javaalgorithmdynamic-programmingpuzzlecoin-change

Finding all permutations to get the given sum (Coin change problem)


I am trying to solve a classical coin-change (dynamic) problem.
To find number of all unique combinations to get a sum from infinite denominations of coins using dynamic approach, i used this method:

/* 
     n - number of coins
     arr[] - coin denominations
     x - total sum
     dp[] - array to store number of combinations at index i.
*/
for (int j = 0; j < n; j++)
     for (int i = 1; i <= x; i++)
          if (arr[j] <= i)
              dp[i] = (long) ((dp[i] + dp[i - arr[j]]) % (1e9 + 7));

This gives me all unique possible combinations count:
Eg:

Input:
n=3 x=9
Coins: 2 3 5

Output:
3

So far ,all good. But i observed that just by interchanging the loops in above snippet, i get all the possible permutations.

for (int i = 1; i <= x; i++)
    for (int j = 0; j < n; j++)
        if (arr[j] <= i)
            dp[i] = (long) ((dp[i] + dp[i - arr[j]]) % (1e9 + 7));

This gives me all unique possible permutations count:
Eg:

Input:
3 9
2 3 5

Output:
8

With debugging and going through each iteration, i mapped a pattern that was formed, but didn't understand the reason behind why i am getting permutations.
Can any one explain me this iteratively. Any help will be appreciated.
Thanks

Both questions can be found here:


Solution

  • The first code with outer loop by coins updates number of ways to compose values dp[] with new coin at every round of outer loop. So after k-th round we have dp[] array filled with combinations of k coins only, and the rest of coins is not used yet. If we will store combinations themselves for sorted coin array, we will see only ordered ones like 1 1 5, and 5 never will go before 1. That is why combinations.

    The second code at m-th round of outer loop fills m-th cell dp[m] using all possible coins. So we count for m=7 both 1 1 5 and 1 5 1 and 5 1 1 variants. That is why all permutations are counted here.


    In addition for comment: we can make 2d array, where dp[x][c] contains number of permutations with sum x, ending with coin a[c]. Note that in this case we have to join counts of permutations with sum x-a[c]. For reference - 1d and 2d Python code.

    def coins1(a, n):   #permutations
        count = [1]+[0]*n
        for x in range(1, n + 1):
            for c in a:
                if (x-c >= 0):
                    count[x] += count[x-c]
        return count[n]
    
    def coins11(a, n):   #permutations 2d
        m = len(a)
        count = [[1] + [0]*(m-1)] + [[0]*m for i in range(n)]
        for x in range(1, n + 1):
            for c in range(m):
                if x>=a[c]:
                    count[x][c] += sum(count[x-a[c]])
        return sum(count[n])