# Combinations Of Coins

**1.Link**

**2. 题目**

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.

**Arguments**

* coins - an array of positive integers representing the different denominations of coins, there are no duplicate numbers and the numbers are sorted by descending order, eg. {25, 10, 5, 2, 1}
* target - a non-negative integer representing the target number of cents, eg. 99

**Assumptions**

* coins is not null and is not empty, all the numbers in coins are positive
* target >= 0
* You have infinite number of coins for each of the denominations, you can pick any number of the coins.

**Return**

* a list of ways of combinations of coins to sum up to be target.
* each way of combinations is represented by list of integer, the number at each index means the number of coins used for the denomination at corresponding index.

**Examples**

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

\[

&#x20; \[0, 4],   (4 cents can be conducted by 0 \* 2 cents + 4 \* 1 cents)

&#x20; \[1, 2],   (4 cents can be conducted by 1 \* 2 cents + 2 \* 1 cents)

&#x20; \[2, 0]    (4 cents can be conducted by 2 \* 2 cents + 0 \* 1 cents)

]



**3. 思路**

1. **Idea: DFS**
2. **For recursion tree, each level represents a coin and each branch in this level represent the count of this coin, so action = coin \* count**
3. **if all coins have been checked, pos == len(action), then check if target ==0. if so, append solution to result list sols**
4. Otherwise, in the coin at position pos of coin list, find the maximum count it can be target//coin. &#x20;
5. For all count <=  target//coin, add action coin\*count to solution and do DFS, then pop that action and check the next action
6. Time: O(B\*H), B = branch of tree,  H = number of coins
7. Space: O(logH) for recursion O(n) for storing results

**4. Coding**

```

class Solution(object):
  def combinations(self, target, coins):
    """
    input: int target, int[] coins
    return: int[][]
    """
    # idea:
    #  pos: position of action, used to select action in each level of tree
    #  in backtracking:
    # each level represents a coin
    # each branch represents count of that coin, so action = coin *  count
    #  1. check if pos == len(action): all actions have been check, then if target == 0 after checking all action, append sol
    #  2. if there is still some actions without checking
    #     find the action/ coins, and use target//coin to find the maximum count of that coin
    #     then the branch in this level =  amount of different cnt of this coin
    #  3. append action with this cnt and update target in the next level
    #  4. pop the cnt action of current coin and choose another cnt action
    sol = []
    sols = []
    self.bt(sols, sol, 0, coins, target)
    return sols
  def bt(self,sols, sol, pos, actions, target):
    
    if pos == len(actions):
      if target == 0:
        sols.append(sol[:])
      return
    a = actions[pos]
    for cnt in range(target//a, -1, -1):
      sol.append(cnt)
      self.bt(sols, sol, pos+1, actions, target - cnt*a)
      sol.pop(-1)
    return 
```







