# Combination Sum IV LeetCode Solution

Difficulty Level Medium

## Problem Statement

Combination Sum IV LeetCode Solution – Given an array of distinct integers `nums` and a target integer `target`, return the number of possible combinations that add up to `target`.

The test cases are generated so that the answer can fit in a 32-bit integer.

```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.```

## Explanation

Think about the recurrence relation first. How does the # of combinations of the `target` related to the # of combinations of numbers that are smaller than the `target`?

So we know that `target` is the sum of numbers in the array. Imagine we only need one more number to reach the target, this number can be anyone in the array, right? So the # of combinations of `target``comb[target] = sum(comb[target - nums[i]]), where 0 <= i < nums.length, and target >= nums[i]`.

In the example given, we can actually find the # of combinations of 4 with the # of combinations of 3(4 – 1), 2(4- 2), and 1(4 – 3). As a result, `comb = comb[4-1] + comb[4-2] + comb[4-3] = comb + comb + comb`.

Then think about the base case. Since if the target is 0, there is only one way to get zero, which is using 0, we can set `comb = 1`.

EDIT: The problem says that the target is a positive integer which makes me feel it’s unclear to put it in the above way. Since `target == 0` only happens when in the previous call, target = nums[i], we know that this is the only combination in this case, so we return 1.

Now we can come up with at least a recursive solution.

The problem is similar to Coin Change II just reverse the order of loops.

// sub problem: permutation(target) is defined as all permutaions of number in nums array that can sum up to target

// state transition: permuation(target) = for each of permutaions in permuations(target – nums[i]), plus element nums[i]

// base case: permutation(0) = {} // let nums = [1, 2, 3]. permutation(1) = permutation(0) add 1 = {1}.

// permuation(2) = permutation(1) add 1 + permuation(0) add 2 = {1, 1} + {2}

// permutation(3) = permuation(2) add 1 + permutation(1) add 2 + permutation(0) add 3 = {1, 1, 1}, {2, 1} + {1, 2} + {3}

// permutation(4) = permuation(3) add 1 + permutation(2) add 2 + permutation(1) add 3 = {1, 1, 1, 1}, {2, 1, 1}, {1, 2, 1} ,{3, 1} // + {1, 1, 2}, {2, 2} + {1, 3}

## Code

### C++ Code for Combination Sum IV

```class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<unsigned int> result(target + 1);
result = 1;
for (int i = 1; i <= target; ++i) {
for (int x : nums) {
if (i >= x) result[i] += result[i - x];
}
}

return result[target];
}
};```

### Java Code for Combination Sum IV

```class Solution {
public int combinationSum4(int[] nums, int target) {
int[] comb = new int[target + 1];
comb = 1;
for (int i = 1; i < comb.length; i++) {
for (int j = 0; j < nums.length; j++) {
if (i - nums[j] >= 0) {
comb[i] += comb[i - nums[j]];
}
}
}
return comb[target];
}
}```

### Python Code for Combination Sum IV

```class Solution:
def combinationSum4(self, N: List[int], T: int) -> int:
dp =  * (T + 1)
dp = 1
for i in range(1, T+1):
for num in N:
if num <= i: dp[i] += dp[i-num]
return dp[T]```

## Complexity Analysis for Combination Sum IV LeetCode Solution

### Time Complexity

O(n*target) since we run two loops.

### Space Complexity

O(target) to store intermediate results.

Translate »