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:

- Permutations: Coin Combinations 1
- Combinations: Coin Combinations 2

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

- Strange behavior when rounding floating point numbers in Java
- Populate JTable Using List
- how to define equivalent of private method in python
- Why does an instance of Test<?> accept non-null objects in the constructor?
- Loading previously stored Keys fails in BouncyCastle with Java
- How to take a photo in Android, using full image size(not thumbnail) and compress the image to bytes?
- How do I recursively disable my components in Swing?
- Validate IPv4 address in Java
- Spring state machine with JPA persistence- Repository usage
- Does using quick build mode for tests change functionality?
- Building a runnable jar with Maven 2
- Explicit wait is not working in Selenium webdriver
- How to find the value which is closest to the series 1, 5, 10, 50, 100, ...?
- How to obtain an Executor?
- appium long press and than move element(drag and drop) is not working
- Java - Two hashmap keys that link to same object value?
- Firestore document returns null values for fields only when the app is downloaded from Google Play; not a problem when loaded via Android Studio
- Is it possible to use Java or Kotlin code in Flutter?
- fatal:unable to update url base from redirection... can't solve it
- maven-compiler-plugin enforce source compatibility with older JDK but compile in newer version
- getting ConstraintViolationException instead of MethodArgumentNotValidException when using @valid with @RequestBody in the controller
- Updating version numbers of modules in a multi-module Maven project
- Open a file's properties window using Java
- Set the JAXB context factory initialization class to be used
- Differences between Executor Channel and Direct Channel - Direct channel doubles messages in case of Failure but Executor channel don't in same case
- Best way to check multiple strings in an if statement
- How to make it so my program doesn't ask for input twice?
- Spring Webflux: FileNotFoundException inside my JAR
- Should I do a check for null for a ResponseEntity<> object in Spring Boot?
- Integration Tests using Testcontainers with OpenLiberty Server throws SocketException