解题思路
先将candidates排序，数组很短，排序很快
然后看最小的元素candidates[0]
如果最小的元素大于等于target，就可以停止递归了
否则，组合包含两种情况
1.有第一项first，然后才是rest的组合
2.没有第一项，都是rest的组合
40. 组合总和 II
代码
cache = {}
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
return cb(candidates, target)
def cb(candidates, target):
key = repr(candidates) + ':' + repr(target)
if key in cache: return cache[key]
if not candidates or candidates[0] > target:
rtv = []
elif candidates[0] == target:
rtv = [[c] for c in candidates if c == target]
else: # candidates[0] < target
first, *rest = candidates
x = cb(rest, target)
y = cb(rest, target-candidates[0])
rtv = x + [[first, *item] for item in y]
cache[key] = dedup(rtv)
return cache[key]
def dedup(s):
x = []
for item in s:
if item not in x:
x.append(item)
return x
