> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/dynamic-programming/377combination-sum-iv.md).

# 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)$$

```python
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?