dynamic-programmingcoin-change# Coin Change - Dynamic Programming - How read all solutions from the DP table

I have seen different solutions to the same problem, but none of them seem to use the approach I used. So here I'm trying to solve the classical coin-change problem in a bottom up dynamic programming approach using a DP table.

```
int[][] dp = new int[nums.length+1][target+1];
for (int i = 0; i <= nums.length; ++i)
dp[i][0] = 1;
for (int i = 1; i < dp.length; ++i) {
for (int j = 1; j < dp[i].length; ++j) {
if (nums[i-1] <= j)
dp[i][j] = dp[i-1][j] + dp[i][j-nums[i-1]];
else
dp[i][j] = dp[i-1][j];
}
}
```

The above code generates the table. For fun if I have: {2,3,5} coins, and want to exchange 8, the table would look like:

```
1 0 0 0 0 0 0 0 0
1 0 1 0 1 0 1 0 1
1 0 1 1 1 1 2 1 2
1 0 1 1 1 2 2 2 3
```

For the above the following method seem to be working well:

```
current <- 4
while (current > 0) do
i <- current
j <- 8
while (j > 0) do
if (dp[i][j] != dp[i-1][j]) then
nums[i-1] is part of the current solution
j <- j-1
else
i <- i-1
end
end
current <- current-1
end
```

Walking through for the above example, we get the following solutions:

```
1) [5,3]
2) [3,3,2]
3) [2,2,2,2]
```

Which is great! At least I thought, until I tried: {1,2} with a T=4. For this the table looks like:

```
1 0 0 0 0
1 1 1 1 1
1 1 2 2 3
```

With the above algorithm to print all solutions, I only get:

```
[2,2]
[1,1,1,1]
```

Which means I won't recover [2,1,1]. So this question is not about the generic how to print the solutions for different approaches to this problem, but how can I read the above DP table to find all solutions.

Solution

Well I have one solution but sure... I can see why the other similar answers are using different approaches for this problem. So the algorithm to generate all the possible answers from the above table looks like:

```
private List<List<Integer>> readSolutions(int[] nums, int[][] dp, int currentRow, int currentColumn, List<Integer> partialSolution) {
if (currentRow == 0) {
return new ArrayList<>();
}
if (currentColumn == 0) {
return new ArrayList<List<Integer>>(Collections.singleton(partialSolution));
}
List<List<Integer>> solutions = new ArrayList<>();
if (dp[currentRow][currentColumn] != dp[currentRow-1][currentColumn]) {
List<Integer> newSolution = new ArrayList<>(partialSolution);
newSolution.add(nums[currentRow-1]);
solutions.addAll(readSolutions(nums, dp, currentRow, currentColumn-nums[currentRow-1], newSolution));
solutions.addAll(readSolutions(nums, dp, currentRow-1, currentColumn, partialSolution));
return solutions;
}
return readSolutions(nums, dp, currentRow-1, currentColumn, partialSolution);
}
```

The logic on the other hand is simple. Take the above table for example:

```
0 1 2 3 4
0 1 0 0 0 0
1 1 1 1 1 1
2 1 1 2 2 3
```

To get a single solution we start from the bottom right corner. If the value does match with the value directly above us, we move up. If it doesn't we move left by the amount corresponding to the row we're in. To generate all answers on on the other hand from the above table...

- we're at some position (i,j)
- if the value at (i-1,j) is the same as (i,j) we make a recursive call to (i-1,j)
- if the values do not match, we have 2 choices...
- we can use the number corresponding to the current row, and recurse into (i,j-n)
- we can skip the number and check if we can create (i,j) instead by using a recursive call to (i-1,j) instead.
- if we reach the first row, we return an empty list
- if we reach the first column, we return what we have already found, which will have the sum of target.

Looks awful right, but works as expected.

- How can I optimize the algorithm to find the longest common subsequence (LCS) between two strings?
- Dynamic Programming - Minimum number of coins in C
- Knapsack with min weight
- Dynamic Programming, create a memo table longest stable subsequence
- What's the reason for the occurrence of Segmentation fault (core dumped)?
- Codility - min average slice
- Minimize array elements by multiplying adjacent elements only if the product is less than equal to k
- Number of contiguous subarrays that contains at least k pairs of duplicates
- Printing Items that are in sack in knapsack
- Dynamic Programming Maximum Profit for Movers in 2 cities
- Issue with Memoization in Recursive Function for Finding Combinations Summing to Target
- Finding least number of moves
- iOS Swift - Leetcode 1567. Maximum Length of Subarray With Positive Product
- Algorithm to 'count the number of ways a floor of size 5*N can be filled with tiles of sizes 1*5 and 2*5'
- Knapsack C# implementation task
- Given an array of houses find how many segments exists after n queries
- minimum number of steps to reduce number to 1
- Python: Writing quite complicated piece of code as a List Comprehension
- LeetCode - Minimum Falling Path Sum - question on memoization
- Reaching vertex d in a tetrahedron in n steps
- Why is the knapsack problem pseudo-polynomial?
- Function to find largest area of a rectangle possible (NOT neccessarily axis parallel) from a list of points
- count of non-empty subsequences with integer average
- Why is closed form for fibonacci sequence not used in practice?
- Number of ways for the Queen
- What's the difference between recursion, memoization & dynamic programming?
- How to find the longest palindromic subsequence (not its length)
- Fibonacci memoization algorithm in C++
- Array of buckets with dynamic programming problem
- Print sequence of tuples before returning a value for valid transactions