377. Combination Sum IV - Explanation

Problem Link

Description

You are 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 = [3,1,2], 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)

Example 2:

Input: nums = [1], target = 3

Output: 1

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i], target <= 1000
• All the elements of nums are unique.

Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        nums.sort()

        def dfs(total):
            if total == 0:
                return 1

            res = 0
            for i in range(len(nums)):
                if total < nums[i]:
                    break
                res += dfs(total - nums[i])
            return res

        return dfs(target)

Time & Space Complexity

• Time complexity: $O(n ^ t)$
• Space complexity: $O(t)$

Where $n$ is the size of the array $nums$ and $t$ is the given target.

---

2. Dynamic Programming (Top-Down)

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        nums.sort()
        memo = { 0 : 1 }

        def dfs(total):
            if total in memo:
                return memo[total]

            res = 0
            for num in nums:
                if total < num:
                    break
                res += dfs(total - num)
            memo[total] = res
            return res

        return dfs(target)

Time & Space Complexity

• Time complexity: $O(n * t)$
• Space complexity: $O(t)$

Where $n$ is the size of the array $nums$ and $t$ is the given target.

---

3. Dynamic Programming (Bottom-Up) - I

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 num in nums:
                dp[total] += dp.get(total - num, 0)

        return dp[target]

Time & Space Complexity

• Time complexity: $O(n * t)$
• Space complexity: $O(t)$

Where $n$ is the size of the array $nums$ and $t$ is the given target.

---

4. Dynamic Programming (Bottom-Up) - II

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        nums.sort()
        dp = defaultdict(int)
        dp[target] = 1
        for total in range(target, 0, -1):
            for num in nums:
                if total < num:
                    break
                dp[total - num] += dp[total]
        return dp[0]

Time & Space Complexity

• Time complexity: $O(n * t)$
• Space complexity: $O(t)$

Where $n$ is the size of the array $nums$ and $t$ is the given target.