# Leetcode Combination Sum IV problem solution

In this Leetcode Combination Sum IV problem solution we have given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target. The answer is guaranteed to fit in a 32-bit integer.

## Problem solution in Python.

```class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp={0:1}
for total in range(1,target+1):
dp[total]=0
for n in nums:
dp[total]+=dp.get(total-n,0)
return dp[target]
```

## Problem solution in Java.

```public int combinationSum4(int[] nums, int target) {
int [] memo= new int[target+1];
memo[0]=1;

for(int i=1;i<memo.length;i++){
for(int j=0;j<nums.length;j++){
if (i-nums[j]>=0){
memo[i]+=memo [i-nums[j]];
}
}
}
return memo[target];
}
```

## Problem solution in C++.

```class Solution {
public:
int dp[1001];
int solve(vector<int>& nums, int n, int t){
if(t<0)
return 0;
if(t==0)
return dp[t]=1;
if(dp[t]!=-1)
return dp[t];
int ans=0;
for(int i=0;i<n;i++){
t-=nums[i];
ans+=solve(nums,n,t);
t+=nums[i];
}
return dp[t]=ans;
}

int combinationSum4(vector<int>& nums, int target) {
int n=nums.size();
memset(dp,-1,sizeof(dp));
int ans=solve(nums,n,target);
return ans;
}
};
```

## Problem solution in C.

```int compare(const void* x, const void* y) {
return *(int*)x - *(int*)y;
}

int combinationSum4(int* nums, int numsSize, int target) {
qsort(nums, numsSize, sizeof(int), compare);

if (target < nums[0])
return 0;

int* dp = (int*)malloc((target + 1)*sizeof(int)), i, j;
memset(dp, 0, (target + 1)*sizeof(int));
dp[0] = dp[nums[0]] = 1;

for (i = nums[0] + 1; i <= target; i++) {
for (j = 0; j < numsSize && i - nums[j] >= 0; j++) {
dp[i] +=  dp[i - nums[j]];
}
}

return dp[target];
}
```