C*******n
发帖数: 24 | 1 Given a number N, write a program that returns all possible combinations of
numbers that add up to N, as lists. (Exclude the N+0=N)
For example, if N=4 return {{1,1,1,1},{1,1,2},{2,2},{1,3}} | l*n
发帖数: 529 | 2 leetcode combination sum
of
【在 C*******n 的大作中提到】
: Given a number N, write a program that returns all possible combinations of
: numbers that add up to N, as lists. (Exclude the N+0=N)
: For example, if N=4 return {{1,1,1,1},{1,1,2},{2,2},{1,3}}
| b*********s
发帖数: 115 | 3 def solution(n):
cache = {}
def helper(target, minVal, allowedZero):
if (target, minVal) in cache:
return cache[(target, minVal)]
if minVal > target:
return []
elif minVal == target:
return [[minVal]]
else:
res = []
for i in range(minVal, target):
tail = helper(target - i, i, True)
for solution in tail:
solution.append(i)
res += tail
if allowedZero:
res.append([target])
cache[(target, minVal)] = res
return res
return helper(n, 1, False) |
|
