## Algorithm

Problem Name: 377. Combination Sum IV

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.

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`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int combinationSum4(int* nums, int numsSize, int target) {
int i, k, n;
#if 0
if (target == 0) return 1;
n = 0;
for (i = 0; i  <  numsSize; i ++) {
k = nums[i];
if (target >= k) {
n += combinationSum4(nums, numsSize, target - k);
}
}
#else
int t, *dp;
dp = calloc((target + 1), sizeof(int));
dp[0] = 1;
for (t = 1; t  < = target; t ++) {    // outer loop target inner loop number => result has dup
for (i = 0; i  <  numsSize; i ++) {  // outer loop number inner loop target => result uniq
k = nums[i];
if (t >= k) {
dp[t] += dp[t - k];
//printf("%d,%d: %d\n", t, k, dp[t]);
}
}
}
n = dp[target];
free(dp);
#endif
return n;
}
``````
Copy The Code &

Input

cmd
nums = [1,2,3], target = 4

Output

cmd
7

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
private:
unordered_map<int, int>m;
public:
int combinationSum4(vector<int>& nums, int target) {
if(target == 0) return 1;
if(m.count(target) > 0) return m[target];
int sum = 0;
for(auto  x: nums)
if(target >= x)
sum += combinationSum4(nums, target - x);
m[target] = sum;
return sum;
}
};
``````
Copy The Code &

Input

cmd
nums = [1,2,3], target = 4

Output

cmd
7

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int combinationSum4(int[] nums, int target) {
Integer[] dp = new Integer[target + 1];
return getCount(target, nums, dp);
}

public int getCount(int target, int[] nums, Integer[] dp) {
if (dp[target] != null) {
return dp[target];
}
if (target == 0) {
return 1;
}
if (target  <  0) {
return 0;
}
int total = 0;
for (int num : nums) {
if (target >= num) {
total += getCount(target - num, nums, dp);
}
}
return dp[target] = total;
}
}
``````
Copy The Code &

Input

cmd
nums = [9], target = 3

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const combinationSum4 = function(nums, target) {
const comb = [1];
for (let i = 1; i  < = target; i++) {
comb[i] || (comb[i] = 0);
for (let j = 0; j  <  nums.length; j++) {
if (i >= nums[j]) {
comb[i] += comb[i - nums[j]];
}
}
}
return comb[target];
};
``````
Copy The Code &

Input

cmd
nums = [9], target = 3

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def combinationSum4(self, nums, target):
memo = {}
def dfs(sm):
if sm in memo:
return memo[sm]
else:
if sm >= target:
memo[sm] = sm == target
return memo[sm]
cnt = 0
for num in nums:
memo[sm + num] = dfs(sm + num)
cnt += memo[sm + num]
return cnt
return dfs(0)
``````
Copy The Code &

Input

cmd
nums = [1,2,3], target = 4

Output

cmd
7