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