Problem Description

You have an unlimited supply of coins with values 1, 2, and 6, but only 2 coins with value 4.

Given an integer n, you need to find the number of ways to make a sum equal to n using these coins.

Key points to understand:

• Coins with values 1, 2, and 6 can be used infinitely many times
• Coins with value 4 can only be used at most twice (you have exactly 2 of them)
• The order of coins doesn't matter - [2, 2, 3] and [2, 3, 2] count as the same way
• Return the result modulo 10^9 + 7 since the answer can be very large

For example, if n = 4, you could make it with:

• Four coins of value 1: [1, 1, 1, 1]
• Two coins of value 2: [2, 2]
• One coin of value 4: [4]
• Two coins of value 1 and one coin of value 2: [1, 1, 2]

The solution uses dynamic programming with a complete knapsack approach for the unlimited coins (1, 2, 6), then adds the cases where we use one or two coins of value 4.

Intuition

The key insight is to separate the problem into two parts: coins we can use unlimited times and coins with limited quantities.

First, let's think about the simpler problem - what if we only had coins of value 1, 2, and 6 (unlimited)? This is a classic complete knapsack problem. We can build up all possible sums from 0 to n using dynamic programming. For each coin value, we check: if we can make sum j - coin_value, then we can also make sum j by adding this coin.

Now, what about the two coins of value 4? Here's the clever part: instead of complicating our dynamic programming with limited quantities, we can handle them separately.

Think of it this way:

• First, calculate all ways to make sum n using only coins 1, 2, and 6
• Then, if we use exactly one coin of value 4, we need to make the remaining sum n - 4 using coins 1, 2, and 6
• If we use both coins of value 4, we need to make the remaining sum n - 8 using coins 1, 2, and 6

Since we've already computed f[j] for all values from 0 to n (where f[j] represents ways to make sum j using coins 1, 2, and 6), we can simply add:

• f[n] (using no coins of value 4)
• f[n-4] (using one coin of value 4, if n >= 4)
• f[n-8] (using two coins of value 4, if n >= 8)

This approach elegantly sidesteps the complexity of tracking limited quantities in our DP state by treating the limited coins as special cases we handle at the end.

Learn more about Dynamic Programming patterns.

Solution Approach

We implement the solution using dynamic programming with the complete knapsack pattern for unlimited coins, then handle the limited coins separately.

Step 1: Initialize the DP array

Create an array f of size n + 1 where f[j] represents the number of ways to make sum j using coins 1, 2, and 6. Initialize f[0] = 1 since there's one way to make sum 0 (use no coins).

f = [0] * (n + 1)
f[0] = 1

Step 2: Complete Knapsack for unlimited coins

For each coin value in coins = [1, 2, 6], iterate through all possible sums from the coin value to n:

for x in coins:
    for j in range(x, n + 1):
        f[j] = (f[j] + f[j - x]) % mod

The key recurrence relation is: f[j] = f[j] + f[j - x]

• f[j] on the right represents ways to make sum j without using coin x
• f[j - x] represents ways to make sum j - x, to which we add coin x to get sum j
• We apply modulo at each step to prevent overflow

Step 3: Handle the limited coins (value 4)

After computing all ways using unlimited coins, we add the cases where we use the coins of value 4:

ans = f[n]  # No coins of value 4
if n >= 4:
    ans = (ans + f[n - 4]) % mod  # Use one coin of value 4
if n >= 8:
    ans = (ans + f[n - 8]) % mod  # Use two coins of value 4

• If n >= 4: We can use one coin of value 4, leaving n - 4 to be made with coins 1, 2, 6
• If n >= 8: We can use both coins of value 4, leaving n - 8 to be made with coins 1, 2, 6

Time Complexity: O(n) - We iterate through the array once for each coin type, and the number of coin types is constant.

Space Complexity: O(n) - We use a single array of size n + 1 to store the DP values.

The beauty of this approach is that it cleanly separates the unlimited and limited coin cases, avoiding the complexity of tracking quantities in the DP state while still correctly counting all possible combinations.

Example Walkthrough

Let's walk through the solution with n = 6.

Step 1: Initialize DP array

f = [1, 0, 0, 0, 0, 0, 0]
     ^
    f[0] = 1 (one way to make 0)

Step 2: Process unlimited coins [1, 2, 6]

Processing coin 1:

• j=1: f[1] = f[1] + f[0] = 0 + 1 = 1
• j=2: f[2] = f[2] + f[1] = 0 + 1 = 1
• j=3: f[3] = f[3] + f[2] = 0 + 1 = 1
• j=4: f[4] = f[4] + f[3] = 0 + 1 = 1
• j=5: f[5] = f[5] + f[4] = 0 + 1 = 1
• j=6: f[6] = f[6] + f[5] = 0 + 1 = 1

After coin 1: f = [1, 1, 1, 1, 1, 1, 1] (Can make any sum using only 1s)

Processing coin 2:

• j=2: f[2] = f[2] + f[0] = 1 + 1 = 2 (now we can use [1,1] or [2])
• j=3: f[3] = f[3] + f[1] = 1 + 1 = 2
• j=4: f[4] = f[4] + f[2] = 1 + 2 = 3 (can use [1,1,1,1], [2,2], or [1,1,2])
• j=5: f[5] = f[5] + f[3] = 1 + 2 = 3
• j=6: f[6] = f[6] + f[4] = 1 + 3 = 4

After coin 2: f = [1, 1, 2, 2, 3, 3, 4]

Processing coin 6:

• j=6: f[6] = f[6] + f[0] = 4 + 1 = 5

After coin 6: f = [1, 1, 2, 2, 3, 3, 5]

The 5 ways to make 6 using coins [1,2,6] are:

• [1,1,1,1,1,1]
• [1,1,1,1,2]
• [1,1,2,2]
• [2,2,2]
• [6]

Step 3: Add limited coins (value 4)

ans = f[6] = 5  # Without using any coin of value 4

# Can we use one coin of value 4?
if 6 >= 4:  # Yes!
    ans = ans + f[6-4] = 5 + f[2] = 5 + 2 = 7
    # The 2 new ways: [4,1,1] and [4,2]

# Can we use two coins of value 4?  
if 6 >= 8:  # No, 6 < 8
    # Skip this

Final answer: 7

The 7 total ways to make sum 6 are:

1. [1,1,1,1,1,1]
2. [1,1,1,1,2]
3. [1,1,2,2]
4. [2,2,2]
5. [6]
6. [1,1,4] (using one coin of value 4)
7. [2,4] (using one coin of value 4)

Solution Implementation

Time and Space Complexity

The time complexity of this algorithm is O(n). The code uses dynamic programming with a bottom-up approach. The outer loop iterates through 3 coin denominations (constant), and for each coin, the inner loop runs from the coin value to n. Since we have a fixed number of coins (3), the total iterations are approximately 3n, which simplifies to O(n).

The space complexity is O(n). The algorithm creates an array f of size n + 1 to store the number of ways to make each amount from 0 to n. This requires O(n + 1) space, which simplifies to O(n). The additional variables (mod, coins, ans) use constant space and don't affect the overall space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Order of Processing Limited Coins

Pitfall: A common mistake is trying to incorporate the limited coins (value 4) directly into the dynamic programming loop alongside unlimited coins. This leads to incorrect counting because the DP state doesn't track how many times we've used the limited coins.

Incorrect Approach:

coins = [1, 2, 4, 6]  # Wrong: treating 4 as unlimited
for coin in coins:
    for j in range(coin, n + 1):
        dp[j] = (dp[j] + dp[j - coin]) % MOD

Solution: Process unlimited and limited coins separately. First complete the DP for unlimited coins, then add contributions from limited coins:

# Step 1: Process unlimited coins
coins = [1, 2, 6]
for coin in coins:
    for j in range(coin, n + 1):
        dp[j] = (dp[j] + dp[j - coin]) % MOD

# Step 2: Add limited coins separately
result = dp[n]
if n >= 4:
    result = (result + dp[n - 4]) % MOD
if n >= 8:
    result = (result + dp[n - 8]) % MOD

2. Forgetting to Apply Modulo Operations

Pitfall: Missing modulo operations during intermediate calculations can cause integer overflow for large values of n.

Incorrect:

dp[j] = dp[j] + dp[j - coin]  # May overflow
# ...
result = dp[n] + dp[n - 4] + dp[n - 8]  # May overflow

Solution: Apply modulo after every addition:

dp[j] = (dp[j] + dp[j - coin]) % MOD
result = (result + dp[n - 4]) % MOD

3. Using 2D DP When 1D is Sufficient

Pitfall: Creating a 2D array dp[i][j] where i represents coins used so far and j represents the sum. This unnecessarily increases space complexity.

Inefficient:

dp = [[0] * (n + 1) for _ in range(len(coins) + 1)]

Solution: Use a 1D array since we only need the previous state:

dp = [0] * (n + 1)

4. Incorrect Handling of Edge Cases

Pitfall: Not checking if n >= 4 or n >= 8 before accessing dp[n - 4] or dp[n - 8], which could cause index out of bounds errors.

Incorrect:

result = dp[n] + dp[n - 4] + dp[n - 8]  # Error if n < 8

Solution: Always check bounds before accessing array indices:

result = dp[n]
if n >= 4:
    result = (result + dp[n - 4]) % MOD
if n >= 8:
    result = (result + dp[n - 8]) % MOD