LeetCode - Combination Sum IV
Problem statement
Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to the target.
The test cases are generated so that the answer can fit in a 32-bit integer.
Problem statement taken from: https://leetcode.com/problems/combination-sum-iv.
Example 1:
Input: nums = [1, 2, 3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Example 2:
Input: nums = [9], target = 3
Output: 0
Constraints:
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 1000
- All the elements of nums are unique
- 1 <= target <= 1000
Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?
Explanation
Backtracking
The problem can be solved using a similar approach we used in our previous blog Combination Sum. The solution generates all the possible combinations that sum up to the target. We then return the count of all such combinations.
The problem only expects us to return the total count, and we can skip generating the combinations using dynamic programming.
Dynamic Programming
Let's check the tree below and try to figure out a solution:
[1, 2, 3], 4
______________________________|_______________________________
1 2 3
[1], 3 [2], 2 [3], 1
________|____________________________
1 2 3
[1, 1], 2 [1, 2], 1 [1, 3], 0
____|__________________________________
1 2 3
[1, 1, 1], 1 [1, 1, 2], 0
We generate all possible combinations and check if the remaining target is 0 or less than 0. When the remaining target is equal to 0, we increment the count. If it's less than 0, we return.
A C++ snippet for the above logic will look as below:
int combinationSum4(vector<int>& nums, int target) {
if (target <= 0) {
return target == 0 ? 1 : 0;
}
int count = 0;
for (int& num : nums) {
count += combinationSum4(nums, target - num);
}
return count;
}As there are many duplicate sub-problems, Dynamic programming can be applied where a duplicate sub-problem solution gets stored in a result array.
Let's check the algorithm first.
- initialize result array of size target + 1
// If the target is zero, then there is a combination
- set result[0] = 1
// loop for each target
- loop for t = 1; t <= target; t++
// for each target, check if there is a combination with all the input nums
- inner loop for num in nums
// skip the numbers if they are greater than current target t
- if t >= num
// add the combinations that we need for the remaining target
- result[t] = result[t] + result[t - num]
- return result[target]
Let's check our solutions in C++, Golang, and Javascript.
C++ solution
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<unsigned int> result(target + 1, 0);
result[0] = 1;
for(int t = 1; t <= target; t++) {
for(int &num : nums) {
if(t >= num) {
result[t] += result[t - num];
}
}
}
return result[target];
}
};Golang solution
func combinationSum4(nums []int, target int) int {
result := make([]int, target + 1)
result[0] = 1
for t := 1; t <= target; t++ {
for _, num := range nums {
if t >= num {
result[t] += result[t - num]
}
}
}
return result[target]
}Javascript solution
var combinationSum4 = function(nums, target) {
let result = Array(target + 1).fill(0);
result[0] = 1;
for(let t = 1; t <= target; t++) {
for(let i = 0; i < nums.length; i++) {
if(t >= nums[i]) {
result[t] += result[t - nums[i]];
}
}
}
return result[target];
};Let's dry run our algorithm for a given input.
Input: nums = [1, 2, 3]
target = 4
Step 1: vector<unsigned int> result(target + 1, 0)
result = [0, 0, 0, 0, 0]
Step 2: result[0] = 1
result = [1, 0, 0, 0, 0]
Step 3: loop for i = 1; i <= target
1 <= 4
true
loop for int &num : nums
num = 1
if t >= num
1 >= 1
true
result[t] = result[t] + result[t - num]
result[1] = result[1] + result[1 - 1]
= 0 + 1
= 1
num = 2
if t >= num
1 >= 2
false
num = 3
if t >= num
1 >= 3
false
i++
i = 2
Step 4: loop for t <= target
2 <= 4
true
loop for int &num : nums
num = 1
if t >= num
2 >= 1
true
result[t] = result[t] + result[t - num]
result[2] = result[2] + result[2 - 1]
= 0 + 1
= 1
num = 2
if t >= num
2 >= 2
true
result[t] = result[t] + result[t - num]
result[2] = result[2] + result[2 - 2]
= 1 + 1
= 2
num = 3
if t >= num
2 >= 3
false
i++
i = 3
Step 5: loop for t <= target
3 <= 4
true
loop for int &num : nums
num = 1
if t >= num
3 >= 1
true
result[t] = result[t] + result[t - num]
result[3] = result[3] + result[3 - 1]
= 0 + 2
= 2
if t >= num
3 >= 2
true
result[t] = result[t] + result[t - num]
result[3] = result[3] + result[3 - 2]
= 2 + 1
= 3
if t >= num
3 >= 3
true
result[t] = result[t] + result[t - num]
result[3] = result[3] + result[3 - 3]
= 3 + 1
= 4
i++
i = 4
Step 6: loop for t <= target
4 <= 4
true
loop for int &num : nums
num = 1
if t >= num
4 >= 1
true
result[t] = result[t] + result[t - num]
result[4] = result[4] + result[4 - 1]
= 0 + 4
= 4
if t >= num
4 >= 2
true
result[t] = result[t] + result[t - num]
result[4] = result[4] + result[4 - 2]
= 4 + 2
= 6
if t >= num
4 >= 3
true
result[t] = result[t] + result[t - num]
result[4] = result[4] + result[4 - 3]
= 6 + 1
= 7
i++
i = 5
Step 7: loop for t <= target
5 <= 4
false
Step 8: return result[target]
result[4]
We return the answer as 7.