Coin Change II

coin_change_II_DFS.java

public class Solution {
    public int result;
    /**
     * @param amount: a total amount of money amount
     * @param coins: the denomination of each coin
     * @return: the number of combinations that make up the amount
     */
    public int change(int amount, int[] coins) {
        // write your code here
        if(coins == null || coins.length == 0 ){
            return -1;
        }
        
        Arrays.sort(coins);
        this.result = 0;
        dfsHelper(amount, coins, new ArrayList<Integer>(),0);
        return this.result;
        
    }
    
    // 計算每一種硬幣的組合，並且判斷如果該組合已大於 amount 則不繼續 dfs。
    // ex. [2] => [2,2],[2,3],[2,8]
    // [3] => [3,2],[3,3],[3,8]
    public void dfsHelper(int amount,
                          int[] coins,
                          ArrayList subCoins,
                          int startIndex
                          ){
        if(amount < 0){
            return;
        }
        
        if(amount == 0){
            this.result++;
            return;
        }
        
        for(int i=startIndex; i < coins.length; i++){
            
            if(i > 0 && coins[i] == coins[i-1]){
                continue;
            }
            
            subCoins.add(coins[i]);
            amount -= coins[i];
            dfsHelper(amount, coins, subCoins, i);
            amount += coins[i];
            subCoins.remove(subCoins.size() - 1);
        }
    }
}