题目描述

题解思路

首先排序数组，然后开始选择数字，当选择数字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 = 0start = 0def dfs():nonlocal sumnonlocal startfor i in range(start, n):num = candidates[i]if sum + num == target:tmp.append(num)res.append([num for num in tmp])tmp.pop()returnif sum + num > target:returnsum += numtmp.append(num)start = idfs()tmp.pop()sum -= numdfs()                return res