Watch the video solution for The Number of Ways to Make the Sum, a medium level problem involving Array, Dynamic Programming. This walkthrough by Programming Live with Larry has 458 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You have an infinite number of coins with values 1, 2, and 6, and only 2 coins with value 4.
Given an integer n, return the number of ways to make the sum of n with the coins you have.
Since the answer may be very large, return it modulo 109 + 7.
Note that the order of the coins doesn't matter and [2, 2, 3] is the same as [2, 3, 2].
Example 1:
Input: n = 4
Output: 4
Explanation:
Here are the four combinations: [1, 1, 1, 1], [1, 1, 2], [2, 2], [4].
Example 2:
Input: n = 12
Output: 22
Explanation:
Note that [4, 4, 4] is not a valid combination since we cannot use 4 three times.
Example 3:
Input: n = 5
Output: 4
Explanation:
Here are the four combinations: [1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [1, 4].
Constraints:
1 <= n <= 105Problem Overview: Given an integer n, compute how many different combinations of coins can produce the exact sum. Some coins can be used unlimited times while a special coin (value 4) has a limited count. Order does not matter, so combinations like 1+2+1 and 2+1+1 count as the same. The task reduces to counting valid coin combinations efficiently.
Approach 1: Dynamic Programming (Complete Knapsack) (Time: O(n), Space: O(n))
This approach models the problem as a classic coin change combinations problem using dynamic programming. Create a dp array where dp[i] represents the number of ways to make sum i. Initialize dp[0] = 1 since one way exists to make sum 0. Iterate through the available coin values and update the DP array in increasing order, adding dp[i - coin] to dp[i]. This works because each coin can be reused indefinitely, which matches the complete knapsack pattern. For coins with limited availability, iterate only for the allowed count or treat them carefully so they are not reused beyond their limit.
The key insight: by iterating coins in the outer loop and sums in the inner loop, each combination is counted once regardless of order. The DP array gradually accumulates the number of valid combinations for every intermediate sum up to n.
Approach 2: Preprocessing + Dynamic Programming (Complete Knapsack) (Time: O(n), Space: O(n))
A cleaner optimization separates unlimited coins from the limited coin. First run a complete knapsack DP using only the unlimited coins (for example values 1, 2, and 6). This preprocessing step computes the number of ways to make every sum up to n using only those coins.
Next incorporate the limited coin (value 4) by enumerating how many times it appears. For each valid count of that coin, subtract its contribution from the target sum and add the number of ways stored in the precomputed DP table. Because the DP table already contains the combinations for the remaining sum, the final answer becomes the sum of those possibilities. This split keeps the DP logic simple and avoids repeatedly recalculating states.
Recommended for interviews: The standard dynamic programming complete knapsack approach is what interviewers expect. It demonstrates you recognize the problem as a coin-change combination variant and can implement a correct dp[i] += dp[i - coin] transition. The preprocessing variation shows deeper understanding of how to separate unlimited and limited items in a DP formulation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Complete Knapsack) | O(n) | O(n) | General case when computing combinations with reusable coins |
| Preprocessing + DP | O(n) | O(n) | Useful when some coins are unlimited and others have limited counts |