Problem

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Note: You can assume that

0 <= amount <= 5000

Example 1:Input: amount = 5, coins = [1, 2, 5]Output: 4Explanation: there are four ways to make up the amount:5=55=2+2+15=2+1+1+15=1+1+1+1+1 Example 2:Input: amount = 3, coins = [2]Output: 0Explanation: the amount of 3 cannot be made up just with coins of 2. Example 3:Input: amount = 10, coins = [10] Output: 1

Solution

DP

class Solution {    public int change(int amount, int[] coins) {        int[] dp = new int[amount+1];        dp[0] = 1;        for (int coin: coins) {            for (int i = 1; i <= amount; i++) {                if (i - coin >= 0) dp[i] += dp[i-coin];            }        }        return dp[amount];    }}

DFS - TLE

class Solution {    int count = 0;    public int change(int amount, int[] coins) {        if (amount == 0) return 1;        dfs(coins, 0, 0, amount);        return count;    }    private void dfs(int[] coins, int start, int sum, int amount) {        if (start == coins.length) return;        if (sum == amount) {            count++;            return;        }        for (int i = start; i < coins.length; i++) {            if (coins[i] + sum > amount) continue;            else dfs(coins, i, sum+coins[i], amount);        }    }}