> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/dfs-permutations/combinations-of-coin.md).

# 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:**&#x20;

For N = coin.length

O(Target^N)

**Space complexity:**&#x20;

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