企业官网建设流程全解析

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 <= 30
• 2 <= candidates[i] <= 40
• candidates的所有元素互不相同
• 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