```
class Solution(object):
def combinationSum4(self, nums, target):
nums, combs = sorted(nums), [1] + [0] * (target)
for i in range(target + 1):
for num in nums:
if num > i: break
if num == i: combs[i] += 1
if num < i: combs[i] += combs[i - num]
return combs[target]
# 17 / 17 test cases passed.
# Status: Accepted
# Runtime: 116 ms
```

This is a 4-line top-down solution that doesn't get accepted due to recursion limit.

```
class Solution(object):
def combinationSum4(self, nums, target, memo=collections.defaultdict(int)):
if target < 0: return 0
if target not in memo:
memo[target] += sum((1, self.combinationSum4(nums, target - num))[target != num]
for num in nums)
return memo[target]
```

The problem with negative numbers is that now the combinations could be potentially of infinite length. Think about `nums = [-1, 1]`

and `target = 1`

. We can have all sequences of arbitrary length that follow the patterns `-1, 1, -1, 1, ..., -1, 1, 1`

and `1, -1, 1, -1, ..., 1, -1, 1`

(there are also others, of course, just to give an example). So we should limit the *length* of the combination sequence, so as to give a bound to the problem.

This is a recursive Python code that solves the above follow-up problem, so far it's passed all my test cases but comments are welcome.

```
class Solution(object):
def combinationSum4WithLength(self, nums, target, length, memo=collections.defaultdict(int)):
if length <= 0: return 0
if length == 1: return 1 * (target in nums)
if (target, length) not in memo:
for num in nums:
memo[target, length] += self.combinationSum4(nums, target - num, length - 1)
return memo[target, length]
```