DP Coin Change Algorithm - Retrieve coin combinations from table

Question

To find how many ways we have of making change for the amount 4 given the coins [1,2,3], we can create a DP algorithm that produces the following table:

table[amount][coins.count]
        0 1 2 3 4
      -----------
(0) 1 | 1 1 1 1 1
(1) 2 | 1 1 2 2 3
(2) 3 | 1 1 2 3 4

The last position being our answer. The answer is 4 because we have the following combinations: [1,1,1,1],[2,1],[2,2],[3,1].

My question is, is it possible to retrieve these combinations from the table I just generated? How?

For completeness, here's my algorithm

func coinChange(coins: [Int], amount: Int) -> Int {
    // int[amount+1][coins]
    var table = Array<Array<Int>>(repeating: Array<Int>(repeating: 0, count: coins.count), count: amount + 1)

    for i in 0..<coins.count {
        table[0][i] = 1
    }

    for i in 1...amount {
        for j in 0..<coins.count {

            //solutions that include coins[j]
            let x = i - coins[j] >= 0 ? table[i - coins[j]][j] : 0
            //solutions that don't include coins[j]
            let y = j >= 1 ? table[i][j-1] : 0

            table[i][j] = x + y
        }
    }
    return table[amount][coins.count - 1];
}

Thanks!

--

Solution

Here's an ugly function that retrieves the combinations, based on @Sayakiss 's explanation:

func getSolution(_ i: Int, _ j: Int) -> [[Int]] {
        if j < 0 || i < 0 {
            //not a solution
            return []
        }
        if i == 0 && j == 0 {
            //valid solution. return an empty array where the coins will be appended
            return [[]]
        }
        return getSolution(i - coins[j], j).map{var a = $0; a.append(coins[j]);return a} + getSolution(i, j - 1)
    }

getSolution(amount, coins.count-1)

Output:

[[1, 3], [2, 2], [1, 1, 2], [1, 1, 1, 1]]

Answer 1

Sure you can. We define a new function get_solution(i,j) which means all solution for your table[i][j]. You can think it returns an array of array, for example, the output of get_solution(4,3) is [[1,1,1,1],[2,1],[2,2],[3,1]]. Then:

• Case 1. Any solution from get_solution(i - coins[j], j) plus coins[j] is a solution for table[i][j].

• Case 2. Any solution from get_solution(i, j - 1) is a solution for table[i][j].

You can prove Case 1 + Case 2 is all possible solution for table[i][j](note you get table[i][j] by this way).

The only problem remains is to implement get_solution(i,j) and I think it's good for you to do it by yourself.

If you still got any question, please don't hesitate to leave a comment here.