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