首先排序数组,然后开始选择数字,当选择数字num后,在去选择大于等于num的合法数字,计算过程中的数字和,直到选数字和等于target, 加入结果集,若数字和大于target则直接退出当前搜索,因为数字是从小到大排序的,如果当前数字和都大于target了,那么之后的选择过程数字和只会更大,所以之后的搜索为无效搜索,直接剪枝
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
n = len(candidates)
candidates.sort()
res = []
tmp = []
sum = 0
start = 0
def dfs():
nonlocal sum
nonlocal start
for i in range(start, n):
num = candidates[i]
if sum + num == target:
tmp.append(num)
res.append([num for num in tmp])
tmp.pop()
return
if sum + num > target:
return
sum += num
tmp.append(num)
start = i
dfs()
tmp.pop()
sum -= num
dfs()
return res