题目描述
候选数组(无重复、可重复选)，找出所有和为 target 的组合。
candidates = [2, 3, 6, 7]
target = 7
输出 = [[2,2,3], [7]]
思路解析
维护一个「剩余 remain」。选了某个数，remain 就减它；remain==0 说明凑齐了，记录组合；remain<0 说明超了，剪枝回头。允许重复选，所以递归时仍从当前数开始（不前进）。
选 2：先选 2，path=[2]，remain = 7−2 = 5。因为能重复，下一步仍可从 2 选起。
再选 2：再选一个 2，path=[2,2]，remain = 3。继续往下。
选 3 · 凑齐：选 3，path=[2,2,3]，remain = 3−3 = 0！凑齐了，记录组合 [2,2,3]，回溯。
回溯试别的 · 死路剪枝：撤销 3，回到 [2,2]（remain=3）。若试 6：3−6 = −3 < 0 超了，剪枝；试更大的也超，这条分支结束。
回到 [2] 试 3：回到 [2]（remain=5）。这一层「用 2」的分支已经试完（得到了 [2,2,3]），for 循环前进到下一个候选 3：[2,3] remain=2，再选 3 超、选更大也超，剪枝。
彻底回溯 · 选 7：撤回到空，从 3、6 开头都凑不出，直到选 7：remain = 7−7 = 0，记录 [7]。所有组合找完：[[2,2,3],[7]]。
把「凑数」变成「剩余目标递减」，到 0 就收、超了就剪——组合总和、目标和、分割等和子集都是这套带剪枝的回溯。
参考代码（Python）
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)) —— 取决于解的数量与深度
- 空间复杂度：O(T/min) —— 递归深度
套路模板
记住骨架：remain==0 收、remain<0 剪、可复用传 i 不可复用传 i+1。换「剩余量」的定义就能套一大类组合搜索。
Python
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] 与 [3,2] 重复）
- ❌ 只在 remain<0 才返回 → ✅ remain==0 也要 return（凑齐后不剪枝会继续加、白做无用功）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。