Combination Sum Iv - Leetcode Solution

Problem Statement:

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.

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

Solution:

In this problem, we need to find the number of ways we can make subsets from given input array which adds up to the target sum.

One of the standard and efficient approaches to solve these kind of problems is to use dynamic programming.

We create an array dp with the length equals to target + 1. Each element of this array dp[i] denotes the number of ways we can form a subset whose sum equals to i.

For each i from 0 to target, we traverse through the input array nums and if nums[j] <= i, we add dp[i - nums[j]] to dp[i] to get the total number of ways to form a subset with i sum.

Finally, we will return dp[target], which will give us the total number of subsets forming the given target sum.

Let's see the code implementation for the above approach:

def combinationSum4(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    dp = [0] * (target + 1)
    dp[0] = 1
    
    for i in range(1, target + 1):
        for j in range(len(nums)):
            if nums[j] <= i:
                dp[i] += dp[i - nums[j]]
                
    return dp[target]

In the given code:

We first initialize dp array with 0 and length target + 1.

Then, we set dp[0] = 1, because only one way we can form a subset with a sum of 0, that is by selecting no element.

After that, we traverse through whole dp array from 1 to target. For each dp[i], we traverse through input array nums and check if nums[j] <= i. If it is True we add dp[i - nums[j]] to dp[i] and get the total number of subsets forming the sum.

Finally, we will return the dp[target] which will give us the total number of subsets forming the target sum.

Time Complexity: O(target * n), where target is the target sum and n is the length of given input array.

Space Complexity: O(target), because we are using an extra array dp of length target + 1.

1