# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://llssff.gitbook.io/coding-problems/dfs-permutations/combinations-of-coin.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.