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.

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.