Coin change but with only 1 of each denomination of coin

Question

The problem is:

The algorithm I came up with is something like:

pair<bool, bitmask>[n][A] memo;     
// memo[i][j].first will be true if its possible to 
// use up to i-th denomination for amt j
// memo[i][j].second will contain info on which 
// denominations are used
for i = 0 to n:
    for j = 1 to A:
    if (i==j): C[i][j] = {true, {i}}
    else if (C[i-1][j].first == true): C[i][j] = C[i-1][j]]
    else if (...see recurrance relation...): 
        C[i][j] = {true, C[i-1][j]+{denom[i]}}
    else: C[i][j] = false

Is it correct so far? But I am not sure how I might proof its correctness ... My attempt looks like just rewriting the code in english ...

For 1st if: we can always use 1 coin of the denomination i to solve amt=i. For 1st else if: if we have a solution for the amt without using the current denomination, we can reuse, that solution. For 2nd else if: if the current denomination can be used (<= amt), and the denomination is not used, we can ...

For complexity: Table is of size nA. And each cell takes O(1) time to fill. Can someone help point me in the right direction?

Answer 1

Yes, I would say that you are totally on the right track here. The problem you are solving is essentially the subset-sum problem and your solution is the standard dynamic programming one (see http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution).

In terms of correctness, I would say that explaining the recurrence relation and the base cases would be fine. As a stylistic point, I would not go through the code and justify every line, but rather focus on the big picture. So just explain what your table represents and how you can set up base cases and recurrence relation and the reader can easily go look at the code and see that you implemented that.

For runtime: Yes, your algorithm is just looping through the elements of the table and filling them in so your explanation is correct.