Problem 400
Problem description here
This is the standard knapsack problem, with addition that we need to return the coins that produce a certain sum.
The problem is for sure a challenging one, as we should implement the coin string creating during the dynamic programming pass.
Here is the final solution:
Highlights
- z[c = b] = b + "" initializes c and z[c] at the same time
- the solution constructs all the best solutions up to 'a' and then just returns the value if it exists