题目描述
候选数组(无重复、可重复选)，找出所有和为 target 的组合。
思路解析
最直接的想法：每个候选数选几次都试一遍，再看哪些和正好等于 target。可这样既会重复(2+3 和 3+2 算两次)，又不知道什么时候该停，一路加到超了还在加。
转折：维护一个「剩余 remain」。选了某个数，remain 就减它；remain==0 说明凑齐了，记录组合；remain<0 说明超了，剪枝回头。再用 start 下标只往后选避免重复——但因为允许重复选，递归时仍从当前数 i 开始(不前进到 i+1)。
选 2：先选 2，path=[2]，remain = 7−2 = 5(大于 0，继续)。因为能重复，下一步仍可从 2 选起。
再选 2：又从 2 选起，再拿一个 2，path=[2,2]，remain = 5−2 = 3。还没到 0，继续往下。
选 3 · 凑齐：这一层从 i=1(数字 3)选起，选 3，path=[2,2,3]，remain = 3−3 = 0！凑齐了，记录组合 [2,2,3]，然后回溯。
回 [2,2] 试 6 · remain<0 剪枝：负例分支：撤销 3 回到 [2,2](remain=3)，for 前进试 6：remain = 3−6 = −3 小于 0，超了 → 剪枝、立刻返回，连递归都不进。试 7 也超，这条分支结束。
回 [2] 试 3：再撤一层回到 [2](remain=5)。「用 2」这支已试完(得到 [2,2,3])，for 前进到下一个候选 3：[2,3] remain=2，往下从 3 选起再选 3 超(2−3小于0)、选更大也超，剪枝。
回到空 · 换 3 打头：彻底撤回到空，for 前进换 3 打头(start=1，不再回头看 2，避免重复)：[3] remain=4，往下 3+3=6 remain=−2 超、3+6 更超，[3,3] 这支也凑不出 7，剪掉。
换 6 打头 · 同样死路：再换 6 打头：[6] remain=1，但 start 锁定只能从 6 往后选，6、7 都比 1 大，remain 必为负 → 剪枝。继续前进到最后一个候选 7。
选 7 · 再收一条：选 7：remain = 7−7 = 0，记录 [7]。候选全试完，所有组合找齐：[[2,2,3], [7]]，和示例对上。
把「凑数」变成「剩余目标递减」，到 0 就收、超了就剪——组合总和、目标和、分割等和子集都是这套带剪枝的回溯。
参考代码（Python）
1res = []
2def backtrack(start, path, remain):
3 if remain == 0: res.append(path[:]); return # 凑齐
4 if remain < 0: return # 超了，剪枝
5 for i in range(start, len(candidates)):
6 path.append(candidates[i])
7 backtrack(i, path, remain - candidates[i]) # 传 i：可重复选
8 path.pop()
9backtrack(0, [], target)复杂度分析
- 时间复杂度：≈ O(N^(T/min)) —— 搜索树最深 T/min 层(每层最多 N 个分支)，由解的数量与深度决定，剪枝大幅砍掉无效枝
- 空间复杂度：O(T/min) —— 递归栈深 = path 最长长度 = target/最小候选数
套路模板
记住骨架：remain==0 收、remain<0 剪、可复用传 i 不可复用传 i+1。换「剩余量」的定义就能套一大类组合搜索。
1def backtrack(start, path, remain):
2 if remain == 0: res.append(path[:]); return
3 if remain < 0: return # 剪枝
4 for i in range(start, n):
5 path.append(a[i])
6 backtrack(i, path, remain - a[i]) # i可复用 / i+1不可复用
7 path.pop()易错点
- 错误写法：递归传 start=0 → 正确写法：可复用传 i、不可复用传 i+1（每层都从 0 开始，会先选 2 再选 3 得 [2,3]，又先选 3 再选 2 得 [3,2]，同一组合重复收集；传 i(或 i+1)只往后选才能去重）
- 错误写法：只在 remain<0 才返回 → 正确写法：remain==0 也要 return（凑齐后若不 return，会在 [2,2,3] 基础上继续加候选，remain 变负做一堆无用功才退）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。