# 377. Combination Sum IV
LeetCode Problem Link (opens new window)
Difficulty: Medium
Given an array of distinct positive integers, find the number of possible combinations that add up to a given positive target integer.
Example:
- nums = [1, 2, 3]
- target = 4
All possible combinations are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
Please note that different sequences are considered different combinations.
Therefore, the output is 7.
# Approach
If you are not familiar with the complete knapsack problem, you can check this article: Knapsack Problem Theory Basics Complete Knapsack (opens new window).
The problem asks for combinations, but it also states that combinations with the same elements in different orders should be counted separately. This essentially means we are looking for permutations!
Understanding the difference between combinations and permutations is crucial.
Combinations do not emphasize order, (1,5) and (5,1) are considered the same combination.
Permutations emphasize order, (1,5) and (5,1) are considered two different permutations.
When studying the backtracking algorithm, many have probably tackled these two problems: 0039.Combination Sum (opens new window) and 0040.Combination Sum II (opens new window). These problems feel similar to this one!
But fundamentally, this problem is looking for the total number of permutations, not listing them.
If the problem required listing all permutations, you'd have to use backtracking to explore all possibilities.
Let’s analyze the five-step dynamic programming approach:
- Define the dp array and the meaning behind its indices.
dp[i]: The number of permutations that sum up to the integer i is dp[i].
- Determine the recurrence relation.
dp[i] (considering nums[j]) can be derived from dp[i - nums[j]] (not considering nums[j]).
Because once you reach nums[j], the permutations count dp[i - nums[j]] is part of dp[i].
In the articles 494. Target Sum (opens new window) and 518. Coin Change II (opens new window), it's explained that to determine the number of ways to fill a knapsack, the recurrence relation is generally dp[i] += dp[i - nums[j]].
This problem is no different.
- How to initialize the dp array.
Due to the dynamic relation dp[i] += dp[i - nums[j]], dp[0] needs to be initialized to 1, so there is a numerical basis when computing other dp[i].
Does dp[0] = 1 have any meaning?
Not really, so I won't force an explanation here because the problem specifies that the target value is a positive integer! So dp[0] = 1 is essentially meaningless and only serves to support the recurrence relationship.
What about the initial values for dp[i] for indices other than 0?
Initialize them to 0 so they don't affect the accumulation of dp[i] with dp[i - nums[j]].
- Decide the traversal order.
The number of items can be used indefinitely, indicating this is a complete knapsack problem.
The resulting set is a permutation, highlighting the need to consider the order among items.
For this problem, the permutation requires iterating in the following nested loop sequence:
To find combinations, loop over items in the outer loop and the knapsack in the inner loop.
To find permutations, loop over the knapsack in the outer loop and items in the inner loop.
If you place the iteration over nums (items) in the outer loop and target in the inner loop: while computing dp[4], the result set only contains collections like {1,3}, and not {3,1}, because nums in the outer loop means 3 can only appear after 1!
Thus, the final iteration sequence is: Place target (knapsack) in the outer loop and nums (items) in the inner loop, iterating items from front to back.
- An example to deduce the dp array.
Let's leverage the example in the prompt for deduction:
If the result returned by the code isn't what you expected, print the dp[i] values and see if they match our deduction.
With the above analysis complete, the C++ code is as follows:
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 0; i <= target; i++) { // Traverse knapsack
for (int j = 0; j < nums.size(); j++) { // Traverse items
if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
- Time complexity: O(target * n), where n is the length of nums
- Space complexity: O(target)
The C++ test case involves two numbers whose sum exceeds the int data type's limit, hence the need to add dp[i] < INT_MAX - dp[i - num] within the if condition.
In contrast, Java does not require this restriction, possibly due to both having int as four bytes or because LeetCode might use different testing data across languages.
# Conclusion
When seeking the number of ways to fill a knapsack, the recurrence relation remains more or less consistent. The key lies in the traversal order!
This problem contrasts sharply with 518. Coin Change II (opens new window), a problem also about permutations and combinations. The traversal order distinguishes them entirely.
A lack of thorough understanding of traversal order in dynamic programming can be quite confusing, and even if the problem has been solved before, its mechanism might remain unclear.
By now, everyone should have a deeper understanding of the traversal order in dynamic programming.
# Other Language Versions
# Java:
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 0; i <= target; i++) {
for (int j = 0; j < nums.length; j++) {
if (i >= nums[j]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
# Python:
Carl's Version
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1
for i in range(1, target + 1): # Traverse knapsack
for j in range(len(nums)): # Traverse items
if i - nums[j] >= 0:
dp[i] += dp[i - nums[j]]
return dp[target]
2
3
4
5
6
7
8
9
Optimized Version
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1) # Create a DP array, storing the total count of combinations
dp[0] = 1 # Initialize the combination count for knapsack capacity of 0 as 1
for i in range(1, target + 1): # Traverse knapsack capacity
for j in nums: # Traverse item list
if i >= j: # When knapsack capacity is greater than or equal to the current item weight
dp[i] += dp[i - j] # Update the total number of combinations
return dp[-1] # Return the total number of combinations when the knapsack capacity is the target
2
3
4
5
6
7
8
9
10
11
2D DP Version
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
# dp[][j] number of combinations that sum up to j
dp = [[0] * (target+1) for _ in nums]
for i in range(len(nums)):
dp[i][0] = 1
# Here we can't initialize dp[0][j]. The value of dp[0][j] depends on dp[-1][j-nums[0]]
for j in range(1, target+1):
for i in range(len(nums)):
if j - nums[i] >= 0:
dp[i][j] = (
# Do not include nums[i]
# When i = 0, dp[-1][j] is exactly 0, so there is no special handling
dp[i-1][j] +
# Include nums[i]. To find the number of combinations that sum up to j,
# we need to attempt every item. Therefore, take the last item dp[-1][j-nums[i]]
dp[-1][j-nums[i]]
)
else:
dp[i][j] = dp[i-1][j]
return dp[-1][-1]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Go:
func combinationSum4(nums []int, target int) int {
// Define dp array
dp := make([]int, target+1)
// Initialize
dp[0] = 1
// Traversal order, first traverse knapsack, then items
for j := 0; j <= target; j++ {
for i := 0; i < len(nums); i++ {
if j >= nums[i] {
dp[j] += dp[j-nums[i]]
}
}
}
return dp[target]
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# JavaScript:
const combinationSum4 = (nums, target) => {
let dp = Array(target + 1).fill(0);
dp[0] = 1;
for(let i = 0; i <= target; i++) {
for(let j = 0; j < nums.length; j++) {
if (i >= nums[j]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
};
2
3
4
5
6
7
8
9
10
11
12
# TypeScript:
function combinationSum4(nums: number[], target: number): number {
const dp: number[] = new Array(target + 1).fill(0);
dp[0] = 1;
// Traverse knapsack
for (let i = 1; i <= target; i++) {
// Traverse items
for (let j = 0, length = nums.length; j < length; j++) {
if (i >= nums[j]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
};
2
3
4
5
6
7
8
9
10
11
12
13
14
# Rust:
impl Solution {
pub fn combination_sum4(nums: Vec<i32>, target: i32) -> i32 {
let target = target as usize;
let mut dp = vec![0; target + 1];
dp[0] = 1;
for i in 1..=target {
for &n in &nums {
if i >= n as usize {
dp[i] += dp[i - n as usize];
}
}
}
dp[target]
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# C
int combinationSum4(int* nums, int numsSize, int target) {
int dp[target + 1];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i = 0; i <= target; i++) {
for (int j = 0; j < numsSize; j++) {
if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
2
3
4
5
6
7
8
9
10
11
12
13
# C#
public class Solution
{
public int CombinationSum4(int[] nums, int target)
{
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 0; i <= target; i++)
{
for (int j = 0; j < nums.Length; j++)
{
if (i >= nums[j] && dp[i] < int.MaxValue - dp[i - nums[j]])
{
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19