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:


  • 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