Combinations Of Coins - Medium-白红宇

Combinations Of Coins - Medium

阅读量：6159 次

发布时间：2019-06-21

本文共 2090 字，大约阅读时间需要 6 分钟。

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

[

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

]

DFS

一共分 n = coins.length 层，每层的分叉数为 amountLeft / coins[i]

time: O(k ^ n), 　　-- n = amount / min(element of coins), k - length of coins

space: O(k ^ n)

public class Solution {  public List
     
      
       > combinations(int target, int[] coins) {    // Write your solution here    List
       
        
         > res = new ArrayList<>();    dfs(target, coins, 0, new ArrayList<>(), res);    return res;  }    private void dfs(int targetLeft, int[] coins, int index, List
         
           list, List
          
           
            > res) { if(index == coins.length - 1) { if(targetLeft % coins[index] == 0) { list.add(targetLeft / coins[index]); res.add(new ArrayList<>(list)); list.remove(list.size() - 1); } return; } int max = targetLeft / coins[index]; for(int i = 0; i <= max; i++) { list.add(i); dfs(targetLeft - i * coins[index], coins, index + 1, list, res); list.remove(list.size() - 1); } }}