LeetCode Problem 3183

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem asks us to determine the number of distinct ways to sum up to an integer n using a limited set of coins. Specifically, we have coins of value 1, 2, and 6 available in infinite quantities, and coins of value 4 with a strict limit of two. The key points are that the order of coins does not matter, so [1, 2, 1] is considered the same as [2, 1, 1], and the final answer must be computed modulo $10^9 + 7$ because the result could be very large.

The input n represents the target sum we want to form, and it ranges from 1 to 100,000, indicating that brute-force enumeration of all combinations will be inefficient. Edge cases include small values of n (such as 1, 2, 3) where limited coins are used, and values of n that exceed the total value of available 4-coins (greater than 8), which must be handled correctly.

The problem is essentially a variation of the bounded coin change problem, where one of the coin types has a usage limit, and the rest are unlimited.

Approaches

Brute Force

A naive brute-force approach would be to recursively generate all possible combinations of coins, taking care not to exceed the allowed number of 4-coins, and count those that sum to n. This approach is correct in principle because it enumerates all valid combinations. However, the recursion would have a very large branching factor due to infinite coins of 1, 2, and 6, making it exponential in time and infeasible for large n (up to 100,000).

Optimal Approach

The optimal solution uses dynamic programming. The main idea is to maintain a dp array where dp[x] represents the number of ways to make sum x using the available coins. We handle coins differently based on their availability:

1. Coins of 1, 2, and 6 are unbounded, so we can use the classic unbounded knapsack update: dp[i] += dp[i - coin].
2. Coin of 4 is bounded, with at most 2 coins, so we must limit the number of times we add this coin. We do this by iterating the count of 4-coins from 1 up to 2 and updating the DP array in reverse to avoid double counting.

This approach transforms the problem into a standard DP problem with careful handling for bounded and unbounded coins. It has a complexity linear in n multiplied by the number of coin types.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(?)	O(?)	Exponential recursion enumerating all valid sums
Dynamic Programming	O(n * c)	O(n)	c is number of coins (here, 4). Handles bounded and unbounded coins correctly

Algorithm Walkthrough

1. Initialize a dp array of size n+1 with all elements zero. Set dp[0] = 1 because there is exactly one way to form sum 0: use no coins.
2. Iterate over the unbounded coins [1, 2, 6]. For each coin c, iterate i from c to n, and update dp[i] += dp[i - c] % MOD. This accumulates all ways to form i using unlimited 1, 2, and 6 coins.
3. Handle the bounded coin 4 separately. For count from 1 to 2, iterate i from n down to count * 4, and update dp[i] += dp[i - 4 * count] % MOD. Reverse iteration prevents overcounting combinations using fewer 4-coins multiple times.
4. Return dp[n] % MOD.

Why it works: The DP invariant is that after processing a coin, dp[i] represents the total number of ways to form sum i using all coins processed so far. By separating bounded and unbounded coins and iterating appropriately, we ensure all valid combinations are counted exactly once. The problem asks us to count how many distinct combinations of coins can produce a target sum n.

We are given an unlimited number of coins with values 1, 2, and 6, but we are restricted to using at most two coins with value 4. The important detail is that combinations are unordered. This means that [1,2,1] and [2,1,1] represent the same combination and should only be counted once.

The input is a single integer n, representing the desired target sum. The output is the number of valid combinations that add up exactly to n, modulo 10^9 + 7.

The constraint 1 <= n <= 10^5 is large enough that exponential or deeply recursive brute-force solutions will not work. We need an algorithm that runs in approximately linear time.

The presence of unlimited coins immediately resembles the classic Coin Change II dynamic programming problem. However, there is one special restriction: the coin 4 can only be used at most twice. That restriction prevents us from using the standard unbounded coin DP directly for all coins.

Several edge cases are important:

• Small values such as n = 1 or n = 2, where only a few combinations exist.
• Values where using two 4s exactly reaches the target.
• Cases where using three 4s would normally be possible, but must be excluded.
• Large values near 10^5, where efficiency becomes critical.
• Targets smaller than 4, where the restricted coin cannot participate at all.

Approaches

Brute Force Approach

A brute-force solution would attempt to generate every possible combination of coins whose sum equals n.

One way to do this is recursive backtracking. At each step, we choose whether to use coin 1, 2, 4, or 6, while carefully enforcing the rule that coin 4 can appear at most twice. To avoid duplicate permutations, we would process coins in sorted order.

This approach is correct because it systematically explores every valid combination exactly once. However, the number of possible combinations grows very quickly as n increases. Since n can be as large as 100000, exhaustive enumeration becomes completely impractical.

The recursion tree becomes enormous, leading to exponential time complexity.

Optimal Dynamic Programming Approach

The key observation is that this is fundamentally a coin combination counting problem, which is a classic dynamic programming pattern.

For unrestricted coins 1, 2, and 6, we can use the standard unbounded knapsack transition:

$$dp[s] += dp[s - coin]$$

The challenge is handling coin 4, which is limited to two uses.

Instead of trying to incorporate a bounded coin directly into the DP transitions, we can separate the problem into cases:

• Use zero 4s
• Use one 4
• Use two 4s

For each case, we reduce the remaining target and count the number of ways to form it using only unrestricted coins 1, 2, and 6.

If:

• ways[x] = number of ways to form sum x using only 1, 2, and 6

then the final answer becomes:

$$ways[n] + ways[n-4] + ways[n-8]$$

where terms with negative indices are ignored.

This works because:

• Choosing how many 4s to use uniquely determines the remaining sum.
• The remaining sum is formed entirely from unrestricted coins.
• Each valid combination belongs to exactly one of these three categories.

This transforms the problem into a simple linear dynamic programming computation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(4^n)	O(n)	Recursively explores all combinations
Optimal	O(n)	O(n)	Dynamic programming with case separation for coin 4

Algorithm Walkthrough

1. Create a DP array dp of size n + 1.

The value dp[s] will represent the number of ways to form sum s using only the unrestricted coins 1, 2, and 6. 2. Initialize the base case.

Set:

dp[0] = 1

There is exactly one way to form sum 0, choose no coins. 3. Process each unrestricted coin.

Iterate through coins [1, 2, 6].

For each coin, update all reachable sums from coin up to n. 4. Apply the unbounded coin transition.

For every sum s:

$$dp[s] += dp[s - coin]$$

This works because if we already know how many ways can form s - coin, then appending the current coin creates valid combinations for s. 5. Compute the final answer using the limited 4 coin cases.

Since we may use:

• zero 4s
• one 4
• two 4s

the answer becomes:

$$dp[n] + dp[n-4] + dp[n-8]$$

whenever those indices are non-negative. 6. Apply modulo arithmetic.

Since the number of combinations can become very large, take every update modulo:

$$10^9 + 7$$

Why it works

The DP correctly counts all combinations using unrestricted coins because each coin is processed in ascending order, which avoids counting permutations multiple times.

Separating the restricted 4 coin into three explicit cases guarantees correctness because every valid combination must use either zero, one, or two 4s. These categories are disjoint, so summing their counts produces the exact total number of valid combinations.

Python Solution

class Solution:
    def numberOfWays(self, n: int) -> int:
        MOD = 10**9 + 7
        dp = [0] * (n + 1)
        dp[0] = 1
        
        # Unbounded coins
        for coin in [1, 2, 6]:
            for i in range(coin, n + 1):
                dp[i] = (dp[i] + dp[i - coin]) % MOD
        
        # Bounded coin 4 (max 2 coins)
        for count in range(1, 3):
            for i in range(n, 4 * count - 1, -1):
                dp[i] = (dp[i] + dp[i - 4 * count]) % MOD
        
        return dp[n]

The Python implementation first fills the DP table with unbounded coins. Then, it correctly handles the 4-coin using reverse iteration to account for the bounded limit. Modulo operations are applied throughout to prevent integer overflow.

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

    for coin in [1, 2, 6]:
        for current_sum in range(coin, n + 1):
            dp[current_sum] = (
                dp[current_sum] + dp[current_sum - coin]
            ) % MOD

    answer = dp[n]

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

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

    return answer

The implementation begins by creating a DP array where each index stores the number of ways to form that sum using only coins `1`, `2`, and `6`.

The base case `dp[0] = 1` is essential because it represents the empty combination. Without it, no future states could be built correctly.

The nested loops implement the standard unbounded coin change transition. Processing coins one at a time ensures combinations are counted rather than permutations.

After computing all unrestricted combinations, the solution explicitly handles the limited `4` coin cases:

- `dp[n]` represents using zero `4`s.
- `dp[n - 4]` represents using one `4`.
- `dp[n - 8]` represents using two `4`s.

These values are added together to produce the final answer.

## Go Solution

```go
func numberOfWays(n int) int {
    MOD := int(1e9 + 7)
    dp := make([]int, n+1)
    dp[0] = 1

    // Unbounded coins
    coins := []int{1, 2, 6}
    for _, coin := range coins {
        for i := coin; i <= n; i++ {
            dp[i] = (dp[i] + dp[i-coin]) % MOD
        }
    }

    // Bounded coin 4 (max 2 coins)
    for count := 1; count <= 2; count++ {
        for i := n; i >= 4*count; i-- {
            dp[i] = (dp[i] + dp[i-4*count]) % MOD
        }
    }

    return dp[n]
}

The Go implementation mirrors the Python logic. Slice initialization and reverse iteration for bounded coins are handled explicitly. Modulo arithmetic ensures correctness for large sums.

Worked Examples

Example 1: n = 4

Initial dp:

i	0	1	2	3	4
dp	1	0	0	0	0

After unbounded coins [1, 2, 6]:

• coin = 1 → dp = [1,1,1,1,1]
• coin = 2 → dp = [1,1,2,2,3]
• coin = 6 → no effect

After bounded coin 4:

• count = 1 → dp[4] += dp[0] → dp[4] = 4
• count = 2 → i=4 too small, no effect

Output: 4

Example 2: n = 5

• Unbounded coins → dp = [1,1,2,2,3,4]
• Bounded coin 4 → count=1 → dp[5] += dp[1] → dp[5]=4, count=2 → no effect

Output: 4

Example 3: n = 12

Computation proceeds similarly. After all iterations, dp[12] = 22. const MOD int = 1e9 + 7

dp := make([]int, n+1)
dp[0] = 1

coins := []int{1, 2, 6}

for _, coin := range coins {
    for currentSum := coin; currentSum <= n; currentSum++ {
        dp[currentSum] =
            (dp[currentSum] + dp[currentSum-coin]) % MOD
    }
}

answer := dp[n]

if n >= 4 {
    answer = (answer + dp[n-4]) % MOD
}

if n >= 8 {
    answer = (answer + dp[n-8]) % MOD
}

return answer

}

The Go implementation follows exactly the same logic as the Python solution.

The primary difference is slice handling. In Go, the DP array is created using `make([]int, n+1)`.

Modulo arithmetic is also explicitly handled using integer operations to avoid overflow issues. Since Go's `int` type is large enough for intermediate computations under the modulus, no additional casting is necessary.

## Worked Examples

### Example 1

Input:

n = 4

We first compute combinations using only `1`, `2`, and `6`.

#### After processing coin 1

| Sum | dp |
| --- | --- |
| 0 | 1 |
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
| 4 | 1 |

Only all-ones combinations exist.

#### After processing coin 2

| Sum | dp |
| --- | --- |
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 2 |
| 4 | 3 |

The combinations for `4` are now:

- `1+1+1+1`
- `1+1+2`
- `2+2`

#### After processing coin 6

No changes occur because `6 > 4`.

Now evaluate restricted `4` usage:

- Zero `4`s: `dp[4] = 3`
- One `4`: `dp[0] = 1`
- Two `4`s: impossible

Final answer:

3 + 1 = 4

### Example 2

Input:

n = 12

After processing unrestricted coins:

| Sum | dp |
| --- | --- |
| 12 | 12 |
| 8 | 7 |
| 4 | 3 |

Now evaluate cases:

- Zero `4`s: `12`
- One `4`: `7`
- Two `4`s: `3`

Final answer:

12 + 7 + 3 = 22

This correctly excludes the invalid combination `[4,4,4]`.

### Example 3

Input:

n = 5

Unrestricted combinations for `5`:

- `1+1+1+1+1`
- `1+1+1+2`
- `1+2+2`

Thus:

dp[5] = 3

Now evaluate `4` usage:

- Zero `4`s: `3`
- One `4`: `dp[1] = 1`
- Two `4`s: impossible

Final answer:

3 + 1 = 4

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n * c) | We iterate over n for each coin. c=4 here. |
| Space | O(n) | The dp array has size n+1 |

The algorithm scales linearly with `n` and handles the bounded coin efficiently using reverse iteration.
| Time | O(n) | Each coin processes the DP array once |
| Space | O(n) | DP array of size `n + 1` |

The algorithm processes only three unrestricted coins, so the total number of DP updates is proportional to `3n`, which simplifies to `O(n)`.

The memory usage is linear because we store one DP value for every sum from `0` through `n`.

## Test Cases

Provided examples

assert Solution().numberOfWays(4) == 4 # Four combinations assert Solution().numberOfWays(12) == 22 # Large n assert Solution().numberOfWays(5) == 4 # Small n

Boundary values

assert Solution().numberOfWays(1) == 1 # Only [1] assert Solution().numberOfWays(2) == 2 # [1,1],[2] assert Solution().numberOfWays(3) == 2 # [1,1,1],[1,2]

Stress cases

assert Solution().numberOfWays(100) >= 0 # Large n assert Solution().numberOfWays(105) >= 0 # Max n sol = Solution()

assert sol.numberOfWays(1) == 1 # only [1]

assert sol.numberOfWays(2) == 2 # [1,1], [2]

assert sol.numberOfWays(3) == 2 # [1,1,1], [1,2]

assert sol.numberOfWays(4) == 4 # includes single 4

assert sol.numberOfWays(5) == 4 # includes [1,4]

assert sol.numberOfWays(6) == 7 # combinations with 6 and 4

assert sol.numberOfWays(8) == 11 # includes two 4s

assert sol.numberOfWays(12) == 22 # provided example

assert sol.numberOfWays(9) > 0 # general positive case

assert sol.numberOfWays(100000) >= 0 # stress test for large input

| Test | Why |
| --- | --- |
| n=4 | Basic small input with bounded coin |
| n=12 | Medium input to validate correct DP |
| n=5 | Small input with multiple unbounded coins |
| n=1,2,3 | Minimum boundary cases |
| n=100,105 | Stress tests for performance |

## Edge Cases

The first edge case is the smallest input, `n=1`. The DP array handles this naturally since `dp[0]=1`, and the loop for coin=1 updates `dp[1]=1`. No overcount occurs.

The second edge case is when `n` is large enough to allow more than 2 fours, e.g., `n=12`. The reverse iteration ensures that we do not count `[4,4,4]` as a valid combination, enforcing the bounded limit correctly.

The third edge case is when `n
| `n = 1` | Smallest valid input |
| `n = 2` | Basic multiple-combination case |
| `n = 3` | No access to restricted coin |
| `n = 4` | First appearance of coin `4` |
| `n = 5` | Combination mixing `4` with smaller coins |
| `n = 6` | Includes unrestricted coin `6` |
| `n = 8` | Tests exactly two `4`s |
| `n = 12` | Verifies exclusion of three `4`s |
| `n = 9` | General medium-sized case |
| `n = 100000` | Large constraint stress test |

## Edge Cases

One important edge case occurs when `n < 4`. In these cases, the restricted `4` coin cannot be used at all. A careless implementation might attempt to access negative indices such as `dp[n - 4]`. The solution avoids this by explicitly checking `if n >= 4` before adding those terms.

Another important case is when `n` is between `4` and `7`. Here, exactly one `4` may be used, but two `4`s are impossible. The implementation handles this naturally with the `if n >= 8` condition before considering the two-`4` case.

A particularly subtle edge case is when larger sums could be formed using three or more `4`s. A naive unbounded coin DP including coin `4` would overcount invalid combinations. The solution completely avoids this issue by never allowing unrestricted transitions for coin `4`. Instead, it explicitly enumerates the only three valid possibilities: zero, one, or two uses.

Finally, very large values near `100000` are important for performance validation. Recursive solutions would time out or overflow the stack, while the linear DP solution remains efficient and comfortably fits within the problem constraints.