# Combination Sum IV – Leetcode Solution

In this post, we are going to solve the 377. Combination Sum IV problem of Leetcode. This problem 377. Combination Sum IV is a Leetcode medium level problem. Let’s see the code, 377. Combination Sum IV – Leetcode Solution.

Contents

## Problem

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

Now, let’s see the code of 377. Combination Sum IV – Leetcode Solution.

# Combination Sum IV – Leetcode Solution

We are going to provide you with the solution using both approaches:

• Memoization – Top-Down Approach
• Tabulation – Bottom-Up Approach

### 377. Combination Sum IV – Solution in Java

This is the code of the Memoization or the Top-Down Approach for the problem perfect square in Java Programming Language.

class Solution {

public int sumMemo(int[] nums, int tar, int[] dp){
if(tar == 0)return 1;
if(tar < 0 ){
return 0;
}
if(dp[tar] != -1)return dp[tar];
int ans=0;
for(int e : nums){
ans += sumMemo(nums,tar-e,dp);
}
return dp[tar] = ans;
}

public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target+1];
Arrays.fill(dp,-1);
return sumMemo(nums,target,dp);
}
}

Now, let’s see the code of the Tabulation or the Bottom-Up Approach for the problem perfect square in Java Programming Language.

class Solution {

public int sumTab(int[] nums, int tar){
int[]dp = new int[tar+1];
dp[0] = 1;
int ans=0;
for(int i=1; i<=tar ; i++)
for(int e:nums){
if(i-e >= 0)
dp[i] += dp[i-e];
}
return dp[tar];
}

public int combinationSum4(int[] nums, int target) {
return sumTab(nums,target);
}
}

### 377. Combination Sum IV – Solution in C++

This is the code of the Memoization or the Top-Down Approach for the problem perfect square in C++ Programming Language.

class Solution {
public:
int sumMemo(vector<int>& nums, int tar, vector<int>& dp){
if(tar == 0)return 1;
if(tar < 0 ){
return 0;
}
if(dp[tar] != -1)return dp[tar];
int ans=0;
for(int e : nums){
ans += sumMemo(nums,tar-e,dp);
}
return dp[tar] = ans;
}

int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target+1,-1);
return sumMemo(nums,target,dp);
}
};

Now, let’s see the code of the Tabulation or the Bottom-Up Approach for the problem perfect square in C++ Programming Language.

class Solution {
public:
int sumTab(vector<int>& nums, int tar){
vector<int>dp(tar+1,0);
dp[0] = 1;
int ans=0;
for(int i=1; i<=tar ; i++)
for(int e:nums){
if(i-e >= 0)
dp[i] += dp[i-e];
}
return dp[tar];
}

int combinationSum4(vector<int>& nums, int target) {
return sumTab(nums,target);
}
};

### 377. Combination Sum IV– Solution in Python

This is the code of the Memoization or the Top-Down Approach for the problem perfect square in Python Programming Language.

class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
#using Memoization
dp = [-1] * target
ans = Solution().solveMemo(nums,target,dp)

return ans

def solveMemo(self,nums: List[int], target: int,dp: List[int])-> int:
count = 0
#Base Case
if(target == 0): return 1
if(target < 0): return 0

if(dp[target-1] != -1):
return dp[target-1]

for num in nums:
count += Solution().solveMemo(nums,target-num,dp)

dp[target-1] = count
return dp[target-1]

Now, let’s see the code of the Tabulation or the Bottom-Up Approach for the problem perfect square in Python Programming Language.

class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
#for tabulation
ans = Solution().solveTab(nums,target)

return ans

def solveTab(self,nums: List[int], target: int)-> int:
dp = [0] * (target +1)
dp[0] = 1

for i in range(target+1):
for num in nums:
if(num <= i):
dp[i] += dp[i-num]
return dp[target]

Note: This problem 377. Combination Sum IV is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.