The Number of Ways to Make the Sum solution and explanation
2 more videos on this problem
The problem
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 <= 105
Approach overview
Problem 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 1: Dynamic Programming (Complete Knapsack)
We can start by ignoring coin 4, defining the coin array coins = [1, 2, 6], and then using the idea of the complete knapsack problem. We define f[j] as the number of ways to make up amount j using the first i types of coins, initially f[0] = 1. Then, we iterate through the coin array coins, and for each coin x, we iterate through amounts from x to n, updating f[j] = f[j] + f[j - x].
Finally, f[n] is the number of ways to make up amount n using coins 1, 2, 6. Then, if n geq 4, we consider choosing one coin 4, so the number of ways becomes f[n] + f[n - 4], and if n geq 8, we consider choosing two coins 4, so the number of ways becomes f[n] + f[n - 4] + f[n - 8].
Note the modulus operation for the answer.
The time complexity is O(n), and the space complexity is O(n). Where n is the amount.
class Solution:
def numberOfWays(self, n: int) -> int:
mod = 10**9 + 7
coins = [1, 2, 6]
f = [0] * (n + 1)
f[0] = 1
for x in coins:
for j in range(x, n + 1):
f[j] = (f[j] + f[j - x]) % mod
ans = f[n]
if n >= 4:
ans = (ans + f[n - 4]) % mod
if n >= 8:
ans = (ans + f[n - 8]) % mod
return ansclass Solution {
public int numberOfWays(int n) {
final int mod = (int) 1e9 + 7;
int[] coins = {1, 2, 6};
int[] f = new int[n + 1];
f[0] = 1;
for (int x : coins) {
for (int j = x; j <= n; ++j) {
f[j] = (f[j] + f[j - x]) % mod;
}
}
int ans = f[n];
if (n >= 4) {
ans = (ans + f[n - 4]) % mod;
}
if (n >= 8) {
ans = (ans + f[n - 8]) % mod;
}
return ans;
}
}class Solution {
public:
int numberOfWays(int n) {
const int mod = 1e9 + 7;
int coins[3] = {1, 2, 6};
int f[n + 1];
memset(f, 0, sizeof(f));
f[0] = 1;
for (int x : coins) {
for (int j = x; j <= n; ++j) {
f[j] = (f[j] + f[j - x]) % mod;
}
}
int ans = f[n];
if (n >= 4) {
ans = (ans + f[n - 4]) % mod;
}
if (n >= 8) {
ans = (ans + f[n - 8]) % mod;
}
return ans;
}
};function numberOfWays(n: number): number {
const mod = 10 ** 9 + 7;
const f: number[] = Array(n + 1).fill(0);
f[0] = 1;
for (const x of [1, 2, 6]) {
for (let j = x; j <= n; ++j) {
f[j] = (f[j] + f[j - x]) % mod;
}
}
let ans = f[n];
if (n >= 4) {
ans = (ans + f[n - 4]) % mod;
}
if (n >= 8) {
ans = (ans + f[n - 8]) % mod;
}
return ans;
}func numberOfWays(n int) int {
const mod int = 1e9 + 7
coins := []int{1, 2, 6}
f := make([]int, n+1)
f[0] = 1
for _, x := range coins {
for j := x; j <= n; j++ {
f[j] = (f[j] + f[j-x]) % mod
}
}
ans := f[n]
if n >= 4 {
ans = (ans + f[n-4]) % mod
}
if n >= 8 {
ans = (ans + f[n-8]) % mod
}
return ans
}Approach 2: Preprocessing + Dynamic Programming (Complete Knapsack)
We can start by preprocessing the number of ways to make up every amount from 1 to 10^5, and then return the corresponding number of ways based on the value of n:
- If
n < 4, directly returnf[n]; - If
4 leq n < 8, returnf[n] + f[n - 4]; - If
n geq 8, returnf[n] + f[n - 4] + f[n - 8].
Note the modulus operation for the answer.
The time complexity is O(n), and the space complexity is O(n). Where n is the amount.
m = 10**5 + 1
mod = 10**9 + 7
coins = [1, 2, 6]
f = [0] * (m)
f[0] = 1
for x in coins:
for j in range(x, m):
f[j] = (f[j] + f[j - x]) % mod
class Solution:
def numberOfWays(self, n: int) -> int:
ans = f[n]
if n >= 4:
ans = (ans + f[n - 4]) % mod
if n >= 8:
ans = (ans + f[n - 8]) % mod
return ansclass Solution {
private static final int MOD = 1000000007;
private static final int M = 100001;
private static final int[] COINS = {1, 2, 6};
private static final int[] f = new int[M];
static {
f[0] = 1;
for (int x : COINS) {
for (int j = x; j < M; ++j) {
f[j] = (f[j] + f[j - x]) % MOD;
}
}
}
public int numberOfWays(int n) {
int ans = f[n];
if (n >= 4) {
ans = (ans + f[n - 4]) % MOD;
}
if (n >= 8) {
ans = (ans + f[n - 8]) % MOD;
}
return ans;
}
}const int m = 1e5 + 1;
const int mod = 1e9 + 7;
int f[m + 1];
auto init = [] {
f[0] = 1;
int coins[3] = {1, 2, 6};
for (int x : coins) {
for (int j = x; j < m; ++j) {
f[j] = (f[j] + f[j - x]) % mod;
}
}
return 0;
}();
class Solution {
public:
int numberOfWays(int n) {
int ans = f[n];
if (n >= 4) {
ans = (ans + f[n - 4]) % mod;
}
if (n >= 8) {
ans = (ans + f[n - 8]) % mod;
}
return ans;
}
};const m: number = 10 ** 5 + 1;
const mod: number = 10 ** 9 + 7;
const f: number[] = Array(m).fill(0);
(() => {
f[0] = 1;
const coins: number[] = [1, 2, 6];
for (const x of coins) {
for (let j = x; j < m; ++j) {
f[j] = (f[j] + f[j - x]) % mod;
}
}
})();
function numberOfWays(n: number): number {
let ans = f[n];
if (n >= 4) {
ans = (ans + f[n - 4]) % mod;
}
if (n >= 8) {
ans = (ans + f[n - 8]) % mod;
}
return ans;
}const (
m = 100001
mod = 1000000007
)
var f [m]int
func init() {
f[0] = 1
coins := []int{1, 2, 6}
for _, x := range coins {
for j := x; j < m; j++ {
f[j] = (f[j] + f[j-x]) % mod
}
}
}
func numberOfWays(n int) int {
ans := f[n]
if n >= 4 {
ans = (ans + f[n-4]) % mod
}
if n >= 8 {
ans = (ans + f[n-8]) % mod
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming (Complete Knapsack) | – |
| Preprocessing + Dynamic Programming (Complete Knapsack) | – |
Complexity analysis
| 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 |
Frequently asked questions
Is The Number of Ways to Make the Sum easy or hard?
The problem is rated Medium because it requires recognizing the coin change combination pattern and correctly handling unlimited versus limited coins. Once mapped to a complete knapsack DP, the implementation becomes straightforward.
The Number of Ways to Make the Sum Python/Java solution
In both Python and Java, implement a dp array of size n+1 and initialize dp[0] = 1. Loop through each coin and update dp[i] += dp[i - coin] for i from coin to n. The same logic works in C++, Go, and TypeScript because the algorithm only uses arrays and loops.
How to solve The Number of Ways to Make the Sum in O(n)?
Use a 1D dynamic programming array. Initialize dp[0] = 1 and iterate through each coin value. For every sum from coin to n, update dp[i] += dp[i - coin]. This complete knapsack transition accumulates the number of combinations in linear time relative to the target sum.
What is the best approach for The Number of Ways to Make the Sum?
The optimal approach uses dynamic programming with the complete knapsack pattern. Maintain a dp array where dp[i] stores the number of ways to form sum i. For each coin, update dp[i] += dp[i - coin]. This runs in O(n) time and O(n) space while counting combinations without considering order.
Is The Number of Ways to Make the Sum asked at Google/Amazon/Meta?
Coin change and knapsack-style dynamic programming problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that count combinations rather than minimum coins are especially common because they test DP state transitions and order handling.
What data structure is used in The Number of Ways to Make the Sum?
The solution mainly relies on a one-dimensional array used for dynamic programming. The dp array stores the number of ways to build each intermediate sum. Iterative updates simulate the complete knapsack process for unlimited coins.
What is the time complexity of The Number of Ways to Make the Sum?
The standard dynamic programming solution runs in O(n) time where n is the target sum. Each coin iterates through the DP array once, and updates are constant time. Space complexity is O(n) for storing the DP table of combination counts.