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.

Description Hints 4 Solution Video 14:47

3183. The Number of Ways to Make the Sum

Medium50.8% acceptancePremium elsewhere, free here

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 10⁹ + 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 <= 10⁵

Topics

Array Dynamic Programming

Hints open one at a time

Hint 1

Consider using dynamic programming.

Hint 2

Define dp[i][x] as the number of ways to make the sum x using only the first i coins; and define coin[i] as the value of coin i.

Hint 3

We can calculate dp[i][x] as the sum of dp[i - 1][x] and dp[i][x - coin[i]].

Hint 4

Remember that 4 can at most be multiplied twice, so we calculate the dp for our infinite coins and then manually handle the existence of 4.

14:47

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

3183. The Number of Ways to Make the Sum

Topics

Hints open one at a time

Similar problems