Leetcode Combination Sum IV problem solution

YASH PAL,

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.

Leetcode Combination Sum IV problem solution

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];
}

coding problems