Coin Change (Count Ways)

Intuition

Unbounded knapsack: dp[i] = number of ways to make sum i using the given coins (each coin can be used any number of times). For each coin, iterate forward through the dp array.

Algorithm

1dp[0]=1, dp[1..sum]=0.
2For each coin c: for w from c to sum: dp[w] += dp[wâˆ’c].
3Return dp[sum].

Example Walkthrough

Input: coins=[1,2,3], sum=4

1.coin=1: dp=[1,1,1,1,1]. coin=2: dp[2]+=dp[0]=2, dp[3]+=dp[1]=2, dp[4]+=dp[2]=3. â†’ dp=[1,1,2,2,3].
2.coin=3: dp[3]+=dp[0]=3, dp[4]+=dp[1]=4. â†’ dp[4]=4.

Output: 4

Common Pitfalls

•Outer loop over coins, inner loop over amounts â€” this counts combinations (not permutations). Swap loops for permutations.

Coin Change (Count Ways).java

Java

// Approach: DP. dp[i] = number of ways to make sum i using given coins.
// For each coin, update dp from coin to sum: dp[j] += dp[j - coin].
// Time: O(n * sum) Space: O(sum)
class Solution {
    public int count(int coins[], int sum) {
        int n = coins.length;
        int dp[] = new int[sum + 1];

        // Base Case: One way to make sum 0 (using no coins)
        dp[0] = 1;

        // Process each coin
        for (int coin : coins) {
            for (int j = coin; j <= sum; j++)
                dp[j] += dp[j - coin]; // Include this coin in forming sum j
        }

        return dp[sum];
    }
}

Was this solution helpful?