377_Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4
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.
Therefore the output is 7.

Solution:

Idea:

• Use the previous example, to get the number of possible combinations for target 4, we need the number of combinations to get target 4-1=3, 4-2=2 and 4-3=1.

• We can store the number of combinations to get 1, 2, 3, 4 for reducing replicated computations.

Time Complexity: $O(mn)$ where m is the target number, n is the length of possible numbers

Space Complexity: $O(m)$

def combinationSum4(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    # nums.sort()  # if nums are not sorted
    output = [1] + [0] * target
    for i in range(1, target + 1):
        for j in nums:
            if i >= j:
                output[i] += output[i - j]
    return output[target]

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?