力扣39-组合总和

39. 组合总和 - 力扣LeetCode给你一个无重复元素的整数数组candidates和一个目标整数target找出candidates中可以使数字和为目标数target的 所有不同组合并以列表形式返回。你可以按任意顺序返回这些组合。candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同则两种组合是不同的。对于给定的输入保证和为target的不同组合数少于150个。示例 1输入candidates [2,3,6,7], target 7输出[[2,2,3],[7]]解释2 和 3 可以形成一组候选2 2 3 7 。注意 2 可以使用多次。7 也是一个候选 7 7 。仅有这两种组合。示例 2输入:candidates [2,3,5], target 8输出:[[2,2,2,2],[2,3,3],[3,5]]示例 3输入:candidates [2], target 1输出:[]提示1 candidates.length 302 candidates[i] 40candidates的所有元素互不相同1 target 40假设 candidates 长度为 n那么可以视为一棵 n 叉树对这棵树进行 dfs 即可。每走到一个节点看当前的路径总和与 target 的大小关系如果大于 target 就回溯如果等于就直接将当前路径的节点值加入答案如果小于就继续往下找。因此也不难看出如果能事先将 candidates 进行排序就可以避免很多不必要的遍历因为如果当前路径加上一个较小的数已经比 target 大了那么比这个数大的数就没必要再考虑加入到路径中了但需要注意的是[2, 2, 3]和[3, 2, 2]是相同的组合也就是说不能单纯地视为 n 叉树需要剪掉一些分支。以示例一为例对于 2 来说它可以选 2 3 6 7那对于 3 来说就没有必要选 2 了因为[2, 3]和[3, 2]是相同的组合所以 3 可选的数只需要是 3 6 7 中的一个。同理对于 6 来说它只需要能选 6 和 7 即可也就是说我们需要设置一个变量 start 表示当前candidates[start]及其之后的数都是可选的。然后这个变量作为递归的一个参数传入即可class Solution: def combinationSum(self, candidates: List[int], target: int) - List[List[int]]: candidates.sort() ans [] def backtrack(start: int, path: List[int], remain: int) - None: # remain 表示离 target 还差多少 if remain 0: ans.append(path[:]) return if remain 0: return for i in range(start, len(candidates)): if candidates[i] remain: # 如果加上当前元素超过 target, 那么这条路径必然不行 break path.append(candidates[i]) backtrack(i, path, remain - candidates[i]) path.pop() backtrack(0, [], target) return ans