Combinations of Coin

Problem:

Given a number of different denominations of coins (e.g., 1 cent, 5 cents, 10 cents, 25 cents), get all the possible ways to pay a target number of cents.

coins = {2, 1}, target = 4, the return should be

[0, 4], (4 cents can be conducted by 0 * 2 cents + 4 * 1 cents)

[1, 2], (4 cents can be conducted by 1 * 2 cents + 2 * 1 cents)

[2, 0] (4 cents can be conducted by 2 * 2 cents + 0 * 1 cents)

Assumptions:

Target >= 0

Coin [ ] != null

No restriction on how many coins used

There will always be a 1 coin

Solution: Recursive DFS

Base Case: When index reach 1 value coin, place remainder into it, print solution[ ]

Recursive Rule:

1. Branch out all valid amounts of current coin

2. Set solution[ ] of current coin to corresponding branch number

3. Call next coin with leftover money

Recursive Tree:

                       {25, 10, 5, 1} Target = 99
                              Branch Values  
25cent level      0           1            2              3
10cent level     0-9         0-7          0-4            0-2
5cent level      0-19        0-14         0-9            0-4
1cent level      4-99        4-74         4-49           2-24

Implementation:

public void combCoins(int[] coin, int moneyLeft, int index, int[] sol){
    if (index == coin.length - 1){
        sol[coin.length - 1] = moneyLeft;
        System.out.println(sol);
        return;
    }
    
    for (int i = 0; i <= moneyLeft/coin[index]; ++i){
        sol[index] = i;
        combCoins(coin, moneyleft - i * coin[index], index + 1, sol);
    )
}

Time complexity:

For N = coin.length

O(Target^N)

Space complexity:

N levels * worst case target = O(N^T)