购物车中没有产品。
39. 组合总和（中等）
Blind 75 › 39. 组合总和（中等） （第 1 章）
题目
给定一个没有重复元素的整数数组 candidates 和一个目标整数 target，找出所有「从 candidates 中选数、数字之和恰好等于 target」的组合。
选数规则有三点：
- 同一个数字可以无限制重复选取。
- 组合不看顺序：
[2,3]与[3,2]视为同一个组合，只计一次。 - 两个组合只要各数字被选次数不同，就视为不同组合。
自造示例：candidates = [2,3,5]，target = 9 → [[3,3,3],[2,2,2,3],[2,2,5]]（组间、组内顺序均可任意）。
再如：candidates = [2,4]，target = 5 → []。
约束：1 ≤ candidates.length ≤ 30；2 ≤ candidates[i] ≤ 40；所有候选数互不相同；1 ≤ target ≤ 40；保证和为 target 的不同组合数少于 150 个。
思路
一句话：把「选哪些数、各选几次」编码成一棵按数组下标推进的决策树，回溯遍历即可。
先想最直白的做法：每次从 candidates 里任选一个数，剩余目标减少，直到减到 0 就记录答案。这样能穷举所有和等于 target 的序列，但会得到大量重复：例如 [2,3] 和 [3,2] 会被当成两个答案。想补救，只能把每条路径排序后放进集合去重，既慢又浪费大量无效搜索。
关键观察：本题的答案是一个多重集——我们只关心每个数字用了多少次，不关心它们被选的先后顺序。因此可以给组合规定一个规范顺序：按 candidates 的下标，从左到右依次决定每个数「用几次」。这样同一个多重集只会被生成一次。
于是每个状态只有两个分支：
- 再用一次
candidates[i]：把candidates[i]放入当前路径，目标减小，下标 i 不变（因为可以无限重复）。 - 以后都不再用
candidates[i]：不放入当前数，下标移动到i+1。
因为所有候选数都是正数，剩余目标会严格递减，递归一定会终止；当剩余为 0 记录答案，剩余为负或下标越界则剪掉。
以 candidates=[2,3,5], target=9 为例，只展开前两层：
| 当前状态 | 分支一：再用一次 candidates[i] | 分支二：跳过 candidates[i] |
|---|---|---|
[], rem 9, i=0 | [2], rem 7, i=0 | [], rem 9, i=1 |
[2], rem 7, i=0 | [2,2], rem 5, i=0 | [2], rem 7, i=1 |
按「先用若干次 2，再考虑 3、5」的顺序展开，[2,3] 会出现，但 [3,2] 永远不会出现，天然去重。
解法
写一个递归函数 dfs(start, remain)，含义是：当前已选路径为 cur，还能从 start 及之后的数字里选择，还需要凑出 remain。
- 若
remain == 0：当前cur是一个答案，复制一份加入结果。 - 若
start越界，或remain < 0：当前分支无效，直接返回。 - 分支一：选
candidates[start]，加入路径，递归dfs(start, remain - candidates[start])，再弹出恢复现场。 - 分支二：跳过
candidates[start]，递归dfs(start + 1, remain)。 - 从
dfs(0, target)开始。
三条命中路径对应自造示例中的三个答案：
| 路径 | 过程 |
|---|---|
[2,2,2, |
还没有评论，来说两句？