The questions are still open and you can try them here.
The question was about linking one transfer request with a list of payments. This question can be generalized to the Subset Sum Problem with strictly positive integers and the guarantee that there is at most one solution. If you don't remember the question, you can also find it below.
There are multiple ways to solve the second question including:
- Recursive way. The idea is that for each payment, there are two possibilities: either the payment is part of the solution or it’s not. We can then solve the problem in a recursive way by trying both possibilities. This solution is less efficient but depending on how you optimize it, you can pass all the test cases.
- Dynamic programming. We can add one payment after another in a set of payments and keep track of all the sums we can reach with the sets of payments in a two-dimensional array. Each cell (p, v) would tell whether there is a subset of the set of payments from 1 to p with a sum equal to v.
We will describe the second way (dynamic programming) since it is more efficient. We would use a two-dimensional array dp[P+1][V+1] where P is the number of payments and V is the value of the transfer request. We actually have the choice between storing booleans, integers or lists of integers in the array. Saving lists of integers means saving the solution directly. Saving booleans means saving whether there is a subset of the payments with a sum being equal to V. We would then need to go through the array a second time to find which payments we should use. We will use lists of integers in this example. Saving integers means saving the index of the latest payment we add to the solution. We would also need to go through the array a second time to find which payments we should use but it would be easier.
There are also other ways to solve the problem with dynamic programming but there are harder to understand.
In pseudo-code, it would look like this:
/*
Read and save the value of the transfer request V.
Read and save the number of payments P.
Initialize the two-dimensional array dp[P+1][V+1]. Each cell is a list of integers.
Initialize the first cell to an empty list (dp[0][0] = new List());
Initialize the array of P payments.
For each payment p from 1 to P,
Read and save the value of the payment in the payments array.
For each value v from 0 to V,
If we can include this payment in the solution (payments[p] >= v && dp[p-1][v - payments[p]] != null),
The list for this set of payments and value is equal to the concatenation of this payment
and the list of payments we need to reach the value v minus the value of the payment
(dp[p-1][v - payments[p]] = new List(dp[p-1][v - payments[p]]).add(p)).
Otherwise,
The list for this set of payments and value is the same than for the previous set of payments (dp[p][v] = dp[p-1][v])
If dp[P+1][V+1] is null,
Output “No result”
Otherwise,
Output the list of integers in dp[P+1][V+1], separated by commas.
*/
We need your help to link the transfer request that Michelle, a TransferWise user, created with the payments that she made. For example, she can create a transfer request of 100 SGD and make payments of 10, 30, 40, 50 SGD. In this case, we need to link transfer request with the payments of 10, 40 and 50 SGD (10 + 40 + 50 = 100). TransferWise will automatically refund the remaining payments (30 SGD) and we don't need to care about this part.
It may happen that Michelle has not paid her transfer entirely. In this case, we don't want to link any payment.
To make things simpler, we guarantee that there is at most one way to link the payments with the transfer request. All the values are positive integers.
Your program should print the ordered list of linked payments separated by spaces. If the transfer request cannot be linked, the program should print "No solution".
The first line contains the SGD value of the transfer request. The next line contains the number of payments P. The next P lines are the SGD values of the payments. All the values are positive integers. Example:
100
4
10
30
40
50
1 <= P < 1000 (number of payments)
Each transfer request and payment is between 1 and 1000000 SGD
Multiple payments can have the same value
There is at most one way to link the payments with the transfer request.
If the transfer request cannot be linked, the program should print "No solution".
Your program should print the ordered list of linked payments separated by spaces. If the transfer request cannot be linked, the program should print "No solution". Example:
10 40 50
100
4
10
30
40
50
10 40 50
The transfer request is for 100 SGD and there are 4 payments of 10, 30, 40 and 50 SGD. The only way to have a sum of 100 SGD with the payments is to sum the payments of 10, 40 and 50 SGD. These are the payments we will link. We want to return "10 40 50".