algoadvance

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The order of the numbers in the combination matters.

Clarifying Questions

  1. Can the numbers in nums be negative? No, all numbers in nums are positive integers.

  2. Can we use the same number multiple times in a combination? Yes, numbers from nums can be reused any number of times.

  3. What is the range of the length of nums and the value of target?

    • 1 <= nums.length <= 200
    • 1 <= nums[i] <= 1000
    • 1 <= target <= 1000

Strategy

To solve this problem, we can use dynamic programming. The idea is to define a dp array where dp[i] represents the number of combinations that sum up to i.

  1. Initialize dp[0] to 1, because there is one way to get a sum of 0, which is to choose nothing.
  2. For each number i from 1 to target, compute dp[i] by iterating through each number in nums. If i - num >= 0, then add dp[i - num] to dp[i].
  3. The result will be in dp[target].

Code

def combinationSum4(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1  # There's one way to make a target 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]

# Example usage:
nums = [1, 2, 3]
target = 4
print(combinationSum4(nums, target))  # Output: 7

Time Complexity

The time complexity of this solution is (O(n \times \text{target})), where (n) is the length of nums. This is because we have two nested loops: one iterating over each value from 1 to target, and another iterating over each integer in nums.

Summary

By using dynamic programming, we are able to store the number of combinations for each possible target sum up to the given target, allowing us to efficiently compute the result.

Try our interview co-pilot at AlgoAdvance.com