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

Question

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:

• Permutations: Coin Combinations 1
• Combinations: Coin Combinations 2

标签： javaalgorithmdynamic-programmingpuzzlecoin-change

Answer 1

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])