# 7-liner in Python, and follow-up question

• ``````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]
``````

• Why not the usual `combs = [1] + [0] * target`?

• ``````class Solution(object):
def combinationSum4(self, nums, target):
nums.sort()
dp = [1] + [0] * target
for i in xrange(target+1):
for n in nums:
if i + n > target:
break
dp[i+n] += dp[i]
return dp[-1]
``````

• '''
class Solution(object):
def combinationSum4(self, nums, target):
nums.sort()
dp = [1] + [0] * target
for i in xrange(target+1):
for n in nums:
if i + n > target:
break
dp[i+n] += dp[i]
return dp[-1]
'''

@ac you have to use the "`" character, not the ' to send code.

• @agave thanks. revised.

• @agave I see you did change combs[0] to 1, but you're not taking advantage of it. You're not even accessing it at all.

• ``````def combinationSum4(self, nums, target):
dp = [1] + [0] * target
for i in range(1, target + 1):
dp[i] = sum([dp[i - c] for c in nums if i >= c])
return dp[-1]
``````

• Regarding the follow-up, how about limiting each number in array to be used only once? Then DP won't work anymore.

• Improved code.

``````    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
combs[i] += combs[i - num]
return combs[target]
``````

• @agave

your code for the followup is not correct

``````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]
``````

The recursive call name is not correct, even if it is correct, the results will also be wrong.
For example:

``````nums = [-1,1,2,3], target = 3, length_limit = 2
``````

the combinations should be:

• [1,2]
• [2,1]
• [3]