Coin Change: Count Ways to Make Sum

·

When working with dynamic programming problems, few are as foundational and insightful as the Coin Change problem. Specifically, the variation that asks: how many different ways can we make a given sum using an infinite supply of specified coin denominations? This article dives deep into solving this classic algorithmic challenge, exploring multiple approaches from brute force to optimized solutions—ideal for coding interviews, competitive programming, and building strong DP intuition.

Whether you're preparing for technical assessments or enhancing your algorithmic toolkit, understanding how to count the number of combinations to reach a target sum is essential. We'll walk through recursive strategies, dynamic programming optimizations, and space-efficient techniques—all while maintaining clarity and performance.

👉 Discover powerful tools to practice coding and algorithm challenges efficiently.

Problem Statement

Given:

Task: Count all possible combinations of coins (with infinite supply) that add up exactly to the given sum.

Important Note: The order of coins does not matter. That is, [1, 2] and [2, 1] are considered the same combination.

Example Walkthrough

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

Combinations:
- [1, 1, 1, 1]
- [1, 1, 2]
- [2, 2]
- [1, 3]

Another example:

Input: sum = 10, coins[] = [2, 5, 3, 6]
Output: 5

Valid combinations include:
- [2, 2, 2, 2, 2]
- [2, 2, 3, 3]
- [2, 2, 6]
- [2, 3, 5]
- [5, 5]

If no combination exists (e.g., sum = 5, coins = [4]), return 0.

Core Keywords

To align with search intent and SEO best practices, here are the core keywords naturally integrated throughout:

These terms reflect common queries in coding interview prep and algorithm learning platforms.

Approach 1: Naive Solution Using Recursion

A natural starting point is recursion. For each coin, we have two choices:

  1. Include the coin: Subtract its value from the sum and recursively solve for the same set of coins.
  2. Exclude the coin: Move to the next coin without changing the sum.

This leads to the recurrence relation:

count(coins, n, sum) = count(coins, n, sum - coins[n-1]) + count(coins, n - 1, sum)

Base Cases

While intuitive, this method has exponential time complexity: O(2^sum) due to repeated subproblems. Space complexity is O(sum) due to recursion depth.

This inefficiency calls for optimization using dynamic programming.

Approach 2: Top-Down DP with Memoization

We improve upon recursion by caching results of subproblems using a 2D memo array.

Key Observations

Steps

  1. Initialize a (n+1) x (sum+1) DP table with -1.
  2. Before computing any state, check if it's already computed.
  3. Store result after computation to avoid redundant calls.

Time Complexity: O(n × sum)
Space Complexity: O(n × sum) + O(sum) recursion stack → still high but vastly better than naive recursion.

👉 Enhance your problem-solving speed with real-time coding environments.

Approach 3: Bottom-Up DP (Tabulation)

Eliminate recursion entirely by building the solution iteratively.

Strategy

Fill a DP table where dp[i][j] represents the number of ways to make sum j using the first i coins.

Transition Logic

For each coin i and each sum j from 0 to sum:

So:

dp[i][j] = dp[i-1][j] + (dp[i][j - coins[i-1]] if coins[i-1] <= j else 0)

Initialize dp[0][0] = 1, and all other dp[0][j] = 0.

This approach avoids recursion overhead and ensures every subproblem is solved once.

Time Complexity: O(n × sum)
Space Complexity: O(n × sum)

Approach 4: Space-Optimized Dynamic Programming

Notice that at any point, we only need:

We can reduce space usage by using a 1D array dp[sum+1].

How It Works

Initialize dp[0] = 1. Then for each coin:

for j from coin_value to sum:
    dp[j] += dp[j - coin_value]

This works because:

Final result is stored in dp[sum].

✅ Time Complexity: O(n × sum)
✅ Space Complexity: O(sum) — optimal!

This technique mirrors the unbounded knapsack pattern and is widely used in production-grade algorithms.

Frequently Asked Questions (FAQ)

Q1: Is this problem similar to Unbounded Knapsack?

Yes! The Coin Change (count ways) problem follows the unbounded knapsack pattern—each item (coin) can be used multiple times. The goal isn’t maximizing value but counting valid combinations.

Q2: What’s the difference between "minimum coins" and "count all ways"?

"Minimum coins" finds the fewest number of coins needed (another variant). Here, we're focused on counting all unique combinations, regardless of length.

Q3: Can I use BFS or DFS instead?

While possible, these approaches suffer from exponential time due to repeated states. DP is preferred for overlapping subproblems.

Q4: Why is the space-optimized version correct when using a 1D array?

Because we process sums in increasing order for each coin. This ensures that dp[j - coin] refers to a state that includes previously processed coins only—preserving correctness without needing full history.

Q5: Does order of coins matter in this solution?

No. By processing one coin type at a time and allowing multiple uses before moving on, we inherently avoid counting permutations like [1,2] and [2,1] separately.

Q6: How do I debug my DP solution?

Start small:

Final Thoughts

The Coin Change problem – count ways to make sum is more than just an interview favorite—it's a gateway to mastering dynamic programming patterns. From recursion to memoization and finally space optimization, each step teaches valuable lessons about efficiency and state management.

Understanding this problem prepares you for related challenges like:

Whether you're aiming for FAANG interviews or improving your coding logic, mastering this pattern pays dividends.

👉 Level up your coding practice with advanced algorithmic tools today.