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 <= 200
• 1 <= nums[i] <= 1000
• All the elements of nums are unique.
• 1 <= target <= 1000

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?

## Combination Sum IV

This problem asks us to find the number of possible combinations that add up to a target value, given an array of distinct integers. The order of the numbers matters, meaning (1, 2, 1) and (1, 1, 2) are considered different combinations.

### 1. Brute Force (Recursion)

A naive approach is to use recursion.  We can explore all possible combinations by trying each number in `nums` as the first number in the combination, and then recursively finding the number of combinations that add up to the remaining target.

```python
def combinationSum4_brute_force(nums, target):
    if target == 0:
        return 1
    if target < 0:
        return 0

    count = 0
    for num in nums:
        count += combinationSum4_brute_force(nums, target - num)
    return count

This approach has overlapping subproblems, leading to exponential time complexity.

2. Dynamic Programming (Memoization)

We can optimize the recursive solution using memoization to store the results of subproblems. This avoids redundant calculations and significantly improves performance.

def combinationSum4_memoization(nums, target):
    memo = {}

    def solve(remaining_target):
        if remaining_target == 0:
            return 1
        if remaining_target < 0:
            return 0

        if remaining_target in memo:
            return memo[remaining_target]

        count = 0
        for num in nums:
            count += solve(remaining_target - num)

        memo[remaining_target] = count
        return count

    return solve(target)

3. Dynamic Programming (Tabulation)

Alternatively, we can use tabulation (bottom-up dynamic programming) to solve this problem. We create a dp array where dp[i] stores the number of combinations that add up to i. We iterate through the dp array and for each value i, we iterate through the nums array and update dp[i + num].

def combinationSum4_tabulation(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1

    for i in range(target):
        if dp[i] > 0: # Optimization: Only iterate if there are valid combinations for the current target
            for num in nums:
                if i + num <= target:
                    dp[i + num] += dp[i]

    return dp[target]

4. Example with Tabulation

Let's trace the tabulation approach with nums = [1, 2, 3] and target = 4:

1. dp = [1, 0, 0, 0, 0] (Initialization: dp[0] = 1)
2. i = 0: dp[0] = 1
   • num = 1: dp[1] += dp[0], so dp[1] = 1
   • num = 2: dp[2] += dp[0], so dp[2] = 1
   • num = 3: dp[3] += dp[0], so dp[3] = 1
   • dp = [1, 1, 1, 1, 0]
3. i = 1: dp[1] = 1
   • num = 1: dp[2] += dp[1], so dp[2] = 2
   • num = 2: dp[3] += dp[1], so dp[3] = 2
   • num = 3: dp[4] += dp[1], so dp[4] = 1
   • dp = [1, 1, 2, 2, 1]
4. i = 2: dp[2] = 2
   • num = 1: dp[3] += dp[2], so dp[3] = 4
   • num = 2: dp[4] += dp[2], so dp[4] = 3
   • dp = [1, 1, 2, 4, 3]
5. i = 3: dp[3] = 4
   • num = 1: dp[4] += dp[3], so dp[4] = 7
   • dp = [1, 1, 2, 4, 7]
6. i = 4: dp[4] = 7

Therefore, dp[4] = 7 is the final answer.

Time Complexity: O(target * n)

• The outer loop iterates up to target. For each value i (0 to target), the inner loop iterates through each number in nums (length n).
• Therefore, the time complexity is proportional to target multiplied by n, which is O(target * n).

Space Complexity: O(target)

• The dp array has a size of target + 1 to store the number of combinations for each value from 0 to target.
• Therefore, the space complexity is O(target).

Follow-up: Negative Numbers

If negative numbers are allowed in the nums array, the problem becomes significantly more complex. Without any constraints, the number of combinations can be infinite. For example, if nums = [-1, 1] and target = 1, we can have combinations like [1], [1, -1, 1], [1, -1, 1, -1, 1], and so on.

To allow negative numbers, we need to add a constraint, such as limiting the length of the combinations. For instance, we can specify that the combinations must have a length less than or equal to a certain value k. This constraint would prevent infinite combinations and make the problem solvable with dynamic programming or recursion with memoization.