Combination Sum IV medium

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 same number from nums may be chosen multiple times in the combination.

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

Steps:

1. Dynamic Programming Approach: We'll use dynamic programming to solve this problem efficiently. We create a DP array dp of size target + 1, where dp[i] represents the number of combinations that sum up to i.

2. Base Case: dp[0] = 1 because there's one way to achieve a sum of 0 (using no numbers).

3. Iteration: We iterate through each number num in nums and then iterate through the dp array from num to target. For each i, we add dp[i - num] to dp[i]. This is because if we can achieve a sum of i - num, we can achieve a sum of i by adding num.

4. Result: After iterating through all numbers in nums, dp[target] will contain the total number of combinations that sum up to target.

Explanation:

The dynamic programming approach avoids redundant calculations by storing the results of subproblems. The key insight is that the number of ways to reach a target sum i is the sum of the number of ways to reach i - num for each number num in nums. This elegantly handles the possibility of using the same number multiple times.

Code:

def combinationSum4(nums, target):
    """
    Calculates the number of combinations that sum up to the target.

    Args:
        nums: A list of distinct integers.
        target: The target sum.

    Returns:
        The number of combinations.
    """
    dp = [0] * (target + 1)
    dp[0] = 1  # Base case: one way to achieve a sum of 0

    for i in range(1, target + 1):
        for num in nums:
            if i - num >= 0:
                dp[i] += dp[i - num]

    return dp[target]

Complexity:

• Time Complexity: O(N * target), where N is the length of nums. We have nested loops iterating through nums and the dp array.
• Space Complexity: O(target). The space used is dominated by the dp array.