Algorithm
Problem Name: 377. Combination Sum IV
Problem Link: https://leetcode.com/problems/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 <= 2001 <= nums[i] <= 1000- All the elements of
numsare 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;
}
Input
Output
#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;
}
};
Input
Output
#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;
}
}
Input
#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];
};
Input
#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)
Input
Output