SYSTEM
算法完整专题笔记:回溯(DFS)专项
src/content/notes/algorithm/回溯.md 统一格式:题号+题目信息 → 题意简述 → 核心思路 → Java完整AC代码 → 通用模板 → 手动模拟要点 → 复杂度 → 总结&易错点 收录全部高频6道经典回溯题: 78.子集、46.全排列、39.组合总和、40.组合总和II、17.电话号码字母组合、22.括号生成
前置回溯基础概念
- 回溯 = 深度优先DFS,暴力枚举所有合法解,通过剪枝减少无效搜索
- 两大核心变量:
path:临时保存当前搜索路径,递归结束必须撤销(回溯恢复现场)res:全局结果集合,存所有合法完整解
- 两大收集规则:
- 子集类:每层递归都收集path(所有路径都是合法子集)
- 组合/排列/括号:仅满足终止条件时收集(完整路径才合法)
- 三种控制不重复方案:
start下标:组合/子集,只向后遍历,不回头,避免[1,2] [2,1]重复visited布尔数组:全排列,标记元素是否已使用- 同层去重
i>start && nums[i]==nums[i-1]:数组含重复元素,防止重复组合
例题1 LC78 子集
题目信息
给互不相同整数数组nums,返回所有子集(幂集),包含空集,顺序不限。 示例:nums=[1,2,3],输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
题意简述
每个元素两种选择:选 / 不选;所有递归路径都是合法子集,每层都收集。 数组无重复,无需去重;使用start保证只向后遍历,无重复组合。
核心思路
- 递归参数
start:只能从start下标向后选,避免乱序重复 - 进入递归立刻拷贝path加入结果(每层都收集)
- 循环选取当前i位置元素,递归
i+1(每个元素只能选一次) - 递归返回后
path.remove回溯撤销
Java完整代码
import java.util.ArrayList;
import java.util.List;
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
backtrack(nums, 0);
return res;
}
void backtrack(int[] nums, int start){
// 每层都收集,所有路径都是子集
res.add(new ArrayList<>(path));
for(int i = start; i < nums.length; i++){
path.add(nums[i]);
backtrack(nums, i + 1);
path.remove(path.size() - 1);
}
}
}
通用模板
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
void backtrack(int[] nums, int start){
res.add(new ArrayList<>(path));
for(int i = start; i < nums.length; i++){
path.add(nums[i]);
backtrack(nums, i+1);
path.remove(path.size()-1);
}
}
模拟要点
nums=[1,2]
-
start=0,path=[] → 存入[]
-
i=0,path=[1] → 存入[1]
,递归start=1
- i=1,path=[1,2] → 存入
[1,2],返回撤销2
- i=1,path=[1,2] → 存入
-
撤销1,i=1,path=[2] → 存入
[2]结果:[], [1], [1,2], [2]
-
复杂度
时间:O(n\cdot2^n),共2^n个子集,每个子集拷贝(O(n)) 空间:(O(n)),递归栈深度等于数组长度
易错点
- 必须
new ArrayList<>(path),直接add(path)会引用覆盖 - 递归参数
i+1,不可写i,否则元素重复选取 - 每层递归第一行收集结果,不是循环结束才收集
例题2 LC46 全排列
题目信息
不含重复数字数组nums,返回全部全排列,顺序不同视为不同解。 示例:nums=[1,2,3],输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
题意简述
可选取前面未使用过的元素,顺序不同算不同解;用visited布尔数组标记元素是否已加入path;仅path长度等于数组长度时收集结果。
核心思路
visited[]标记下标,true代表已选,循环跳过已访问元素- 终止条件:path.size() == nums.length,收集完整排列
- 循环从i=0开始遍历全部元素(可以回头选前面数字)
- 选当前元素标记visited[i]=true,递归,返回后撤销标记与path
Java完整代码
import java.util.ArrayList;
import java.util.List;
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] visited;
public List<List<Integer>> permute(int[] nums) {
visited = new boolean[nums.length];
backtrack(nums);
return res;
}
void backtrack(int[] nums){
// 仅完整排列才收集
if(path.size() == nums.length){
res.add(new ArrayList<>(path));
return;
}
for(int i = 0; i < nums.length; i++){
if(visited[i]) continue;
visited[i] = true;
path.add(nums[i]);
backtrack(nums);
path.remove(path.size()-1);
visited[i] = false;
}
}
}
通用模板
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] visited;
void backtrack(int[] nums){
if(path.size() == nums.length){
res.add(new ArrayList<>(path));
return;
}
for(int i=0; i<nums.length; i++){
if(visited[i]) continue;
visited[i] = true;
path.add(nums[i]);
backtrack(nums);
path.remove(path.size()-1);
visited[i] = false;
}
}
模拟要点
nums=[1,2]
- path空,visited全false
- i=0,visited[0]=true,path=[1],递归
- i=0跳过,i=1未访问,path=[1,2],长度2存入结果
- 撤销,i=1,path=[2],递归i=0,path=[2,1]存入结果
- i=0,visited[0]=true,path=[1],递归
复杂度
时间:O(n\cdot n!),n!种排列,每种拷贝(O(n)) 空间:(O(n)),递归栈+visited数组
易错点
- 循环i从0开始,不用start,和子集区分开
- 回溯必须同时撤销path和visited标记,缺一不可
- 仅叶子节点收集结果,不要每层收集
例题3 LC39 组合总和
题目信息
无重复元素数组candidates,目标target;同一数字可无限次选取,返回和为target的不重复组合。 示例:candidates=[2,3,6,7], target=7,输出[[2,2,3],[7]]
题意简述
组合不区分顺序,不能出现[2,3] [3,2];使用start保证只向后选;递归传i而非i+1,允许重复选取当前数字。
核心思路
- start控制只向后遍历,避免重复组合
- sum记录当前路径和,sum>target直接剪枝返回
- sum==target收集结果
- 递归参数i不变,代表下一轮仍可选当前数字(无限选取)
Java完整代码
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
backtrack(candidates, target, 0, 0, path, res);
return res;
}
void backtrack(int[] candidates, int target, int start, int sum, List<Integer> path, List<List<Integer>> res){
if(sum == target){
res.add(new ArrayList<>(path));
return;
}
if(sum > target) return;
for(int i = start; i < candidates.length; i++){
path.add(candidates[i]);
backtrack(candidates, target, i, sum + candidates[i], path, res);
path.remove(path.size()-1);
}
}
}
通用模板
void backtrack(int[] nums, int target, int start, int sum, List<Integer> path, List<List<Integer>> res){
if(sum == target){
res.add(new ArrayList<>(path));
return;
}
if(sum > target) return;
for(int i = start; i < nums.length; i++){
path.add(nums[i]);
backtrack(nums, target, i, sum + nums[i], path, res);
path.remove(path.size()-1);
}
}
模拟要点
[2,3,6,7], target=7 i=0选2,递归仍从i=0,可重复选2;sum=4再选3总和7,存入[2,2,3];最后i=3直接选7存入[7]
复杂度
时间:O(2^n),最坏所有数字都选 空间:(O(target)),递归栈深度最大为target/min(nums)
易错点
- 递归传
i,不是i+1,i+1则每个元素只能选一次(变成40题逻辑) - start不能从0开始循环,否则生成乱序重复组合
- 提前剪枝sum>target,减少无效递归
例题4 LC40 组合总和II
题目信息
数组含重复数字,每个元素仅能使用一次;返回和为target的无重复组合。 示例:candidates=[10,1,2,7,6,1,5], target=8,输出[[1,1,6],[1,2,5],[1,7],[2,6]]
题意简述
两大约束:1. 元素只能选一次,递归i+1;2. 数组存在重复数字,同层循环去重防止重复组合。
核心思路
- 先排序,将相同数字聚拢,用于同层去重
- 循环判断:
i>start && candidates[i]==candidates[i-1],同层重复直接跳过 - 递归参数i+1,每个元素只能选取一次
- sum剪枝,等于target收集结果
Java完整代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
Arrays.sort(candidates);
backtrack(candidates, target, 0, 0, path, res);
return res;
}
void backtrack(int[] candidates, int target, int start, int sum, List<Integer> path, List<List<Integer>> res){
if(sum == target){
res.add(new ArrayList<>(path));
return;
}
if(sum > target) return;
for(int i = start; i < candidates.length; i++){
// 同层去重核心代码
if(i > start && candidates[i] == candidates[i-1]) continue;
path.add(candidates[i]);
backtrack(candidates, target, i+1, sum + candidates[i], path, res);
path.remove(path.size()-1);
}
}
}
通用模板
void backtrack(int[] nums, int target, int start, int sum, List<Integer> path, List<List<Integer>> res){
if(sum == target){
res.add(new ArrayList<>(path));
return;
}
if(sum>target) return;
for(int i=start; i<nums.length; i++){
if(i>start && nums[i]==nums[i-1]) continue;
path.add(nums[i]);
backtrack(nums, target, i+1, sum+nums[i], path, res);
path.remove(path.size()-1);
}
}
模拟要点
排序后[1,1,2,5,6,7,10] 第一层i=0选1,递归搜出[1,1,6];第一层i=1时i>start(0)且数字相同,直接跳过,避免重复组合。
复杂度
同39组合总和,排序额外增加O(n\log n)
易错点
- 必须先排序,否则同层去重失效
- 去重条件是
i>start而非i>0,否则会删掉[1,1,6]这类合法含重复元素的组合 - 递归参数i+1,不可写i
例题5 LC17 电话号码的字母组合
题目信息
仅含2-9的数字字符串,返回所有按键字母笛卡尔积组合;1无对应字母。 映射:2=abc,3=def,4=ghi,5=jkl,6=mno,7=pqrs,8=tuv,9=wxyz 示例:digits="23",输出["ad","ae","af","bd","be","bf","cd","ce","cf"]
题意简述
分层搜索,index代表当前处理第几位数字;每层仅遍历当前数字对应的字母集合,无start、无visited;字符串拼接无需手动撤销path。
核心思路
- 建立数字→字母映射数组
- index标记当前处理到第几个数字,终止条件index等于字符串长度
- 遍历当前数字所有对应字母,拼接字符串递归index+1
- Java字符串不可变,
path + c自动生成新串,不用remove回溯
Java完整代码
import java.util.ArrayList;
import java.util.List;
class Solution {
String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if(digits.isEmpty()) return res;
backtrack(digits, 0, "", res);
return res;
}
void backtrack(String digits, int index, String path, List<String> res){
if(index == digits.length()){
res.add(path);
return;
}
int num = digits.charAt(index) - '0';
String letters = map[num];
for(char c : letters.toCharArray()){
backtrack(digits, index + 1, path + c, res);
}
}
}
通用模板
String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
void backtrack(String digits, int index, String path, List<String> res){
if(index == digits.length()){
res.add(path);
return;
}
String letters = map[digits.charAt(index)-'0'];
for(char c : letters.toCharArray()){
backtrack(digits, index+1, path + c, res);
}
}
模拟要点
digits=“23” index=0处理数字2(a/b/c),每一个字母进入index=1处理数字3(d/e/f),拼接后长度2存入结果。
复杂度
时间:O(3^m \cdot 4^n),m是对应3字母数字,n对应4字母数字 空间:(O(len(digits))),递归栈深度等于数字长度
易错点
- 输入空字符串直接返回空列表,不能返回
[""] - index是数字下标,不要混淆字母循环下标
- 字符串拼接无需手动回溯撤销
例题6 LC22 括号生成
题目信息
n对括号,生成全部有效括号组合;有效规则:任意前缀左括号≥右括号,总左右括号数量相等。 示例:n=3,输出["((()))","(()())","(())()","()(())","()()()"]
题意简述
每层仅两种选择:加( 或加),带合法性剪枝;用open/close记录已使用左右括号数量。
核心思路
- open:已使用左括号,open < n 才能新增左括号
- close:已使用右括号,close < open 才能新增右括号(保证前缀合法)
- 终止条件:open == n && close == n,收集字符串
- 字符串拼接无需手动回溯撤销
Java完整代码
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
backtrack(res, "", 0, 0, n);
return res;
}
void backtrack(List<String> res, String path, int open, int close, int n){
if(open == n && close == n){
res.add(path);
return;
}
if(open < n){
backtrack(res, path + "(", open + 1, close, n);
}
if(close < open){
backtrack(res, path + ")", open, close + 1, n);
}
}
}
通用模板
void backtrack(List<String> res, String path, int open, int close, int n){
if(open == n && close == n){
res.add(path);
return;
}
if(open < n) backtrack(res, path + "(", open+1, close, n);
if(close < open) backtrack(res, path + ")", open, close+1, n);
}
模拟要点
n=2 open=0先加(,open=1可再加(或);只有close<open时才能加右括号,不会生成())(非法串。
复杂度
时间:O(\frac{4^n}{\sqrt{n}}) 卡特兰数复杂度 空间:(O(n)),递归栈深度为(2^n)
易错点
- 右括号条件不能写成
close < n,必须close < open,否则产生非法括号 - 优先递归左括号分支,减少无效搜索
- 字符串自动拼接,不用手动删除字符
📊回溯6道题核心区分速查表
| 题号 | 题目 | 数组有无重复 | 能否重复选元素 | 控制去重手段 | 收集时机 | 递归关键参数 |
|---|---|---|---|---|---|---|
| 78 | 子集 | 无 | 不能 | start(i+1) | 每层递归都收集 | start |
| 46 | 全排列 | 无 | 不能 | visited布尔数组 | 仅完整路径收集 | i从0遍历+visited |
| 39 | 组合总和 | 无 | 可以 | start(i) | 完整路径收集 | start,递归传i |
| 40 | 组合总和II | 有 | 不能 | start(i+1)+同层去重i>start | 完整路径收集 | start+i>start去重判断 |
| 17 | 电话号码字母组合 | 无分层候选 | 分层单次选取 | index分层控制 | 长度匹配收集 | index处理数字位 |
| 22 | 括号生成 | 无 | 二选一 | open/close数量限制 | 括号总数匹配收集 | open、close计数 |
回溯通用踩坑总览
- path引用陷阱:List类型path必须
new ArrayList<>(path)拷贝存入结果,String拼接无此问题 - 回溯恢复现场:List添加元素后必须remove最后一位;visited标记必须递归返回后重置false
- 组合vs排列:组合用start不回头;排列用visited从头遍历
- 重复数组去重:40题必须排序+同层i>start判断,不能仅i>0
- 可重复选取:39递归传i;不可重复统一传i+1
- 剪枝优先:sum>target、括号非法、数字超限提前return,大幅降低递归量
回溯算法全套优化方法(面试高频,配套前面回溯专题笔记)
一、剪枝优化(最核心、提效最明显,所有回溯题通用)
剪枝:在递归进入下一层之前,提前判断这条路径不可能得到合法解,直接放弃这条分支,不再递归。
1. 和/数值类提前剪枝(39/40组合总和、子集)
适用场景:求和、求目标值类题目
- 规则:当前路径和
sum > target,直接 return,不再循环后续更大数字 - 进阶优化:数组先升序排序,一旦
sum + candidates[i] > target,后面循环全部break(有序,后面数字只会更大) 示例代码(组合总和II排序后内层循环)
for(int i = start; i < candidates.length; i++){
if(sum + candidates[i] > target) break; // 排序后直接跳出循环,大量剪枝
if(i>start && candidates[i]==candidates[i-1]) continue;
...
}
2. 合法性剪枝(22括号生成)
不生成非法路径,从源头减少递归:
- 右括号数量不能超过左括号
close < open才能加) - 左括号总数不能超过n
open < n才能加(完全避免())(这类无效括号分支。
3. 长度/数量剪枝(77组合、子集、全排列)
- 求固定长度k的组合:path.size() >= k 直接终止
- 剩余可选数字不够凑目标长度:
path.size() + 剩余可用数字 < k,直接break 示例:要选3个数字,当前path已有1个,剩下只有1个数字,不可能凑齐,剪枝。
4. 上下界范围剪枝
限定数字取值区间,超出范围直接跳过。
二、去重优化(针对数组含重复元素,40组合总和II、90子集II)
目标:避免生成完全相同的组合,减少重复递归与结果冗余
1. 预处理排序(前置必要操作)
将数组升序排列,相同数字相邻,才能实现同层去重。
2. 同层循环去重(核心)
// 同层:i>start 代表不是本层第一个元素,且和前一个数字相等,直接跳过
if(i > start && nums[i] == nums[i-1]) continue;
易错区分:
i>start:只禁止同一层重复选取,允许不同层级重复(如[1,1,6]合法解能保留)- 若写成
i>0:会把跨层合法重复数字直接剪掉,丢失答案
3. 分层标记去重(全排列II,有重复元素)
用visited数组,同一层跳过相同且前一个未访问的数字,避免重复排列。
三、循环范围缩小优化(start下标控制,组合/子集专用)
1. start下标,只向后遍历,杜绝乱序重复组合
组合类题目(78子集、39、40)循环从start开始,不再从头i=0遍历,天然不会生成[1,2]和[2,1]两套重复分支,直接减半搜索量。 对比:
- 全排列不用start,i从0遍历;
- 组合必须用start,大幅减少分支数量。
2. 尾部截断缩小循环边界
计算剩余可选取元素数量,达不到目标长度直接break,不用完整循环数组。
四、数据结构优化(减少拷贝、降低内存开销)
1. 路径存储优化
- List路径:递归结束必须手动
remove(path.size()-1)复用同一个path对象,不每次新建List; - String路径(17电话号码、22括号):字符串不可变,
path + "c"每次生成新字符串,无需手动回溯删除,代码简洁,但频繁拼接有开销;海量分支可改用StringBuilder优化:
// StringBuilder版本括号生成,减少字符串新建
void backtrack(StringBuilder sb, int open, int close, int n, List<String> res){
if(open == n && close == n){
res.add(sb.toString());
return;
}
if(open < n){
sb.append('(');
backtrack(sb, open+1, close, n, res);
sb.deleteCharAt(sb.length()-1); // 手动回溯删除
}
if(close < open){
sb.append(')');
backtrack(sb, open, close+1, n, res);
sb.deleteCharAt(sb.length()-1);
}
}
2. 结果存入优化
存入结果时必须拷贝路径:res.add(new ArrayList<>(path)) 如果直接res.add(path),后续回溯修改path会覆盖已保存的结果;但只拷贝满足条件的路径,不提前拷贝,减少对象创建。
3. 标记数组复用
boolean[] visited 全局只创建一次,递归中仅修改true/false,不每次新建数组。
五、递归层面优化
1. 尾递归(部分语言支持,Java不推荐)
Java虚拟机不优化尾递归,递归深度大仍会栈溢出,C++/Python可使用。
2. 减少递归参数传递
将不变参数(数组、target、n)提升为全局成员变量,不用每次递归入参传递,减少栈内存开销。 示例:
// 全局变量,不用每次递归携带
int[] candidates;
int target;
List<List<Integer>> res;
3. 迭代式回溯(手动栈替代递归,解决栈溢出)
递归深度极大时(如n>1000),会抛出StackOverflowError;用Deque手动模拟DFS栈,转化迭代写法,规避栈溢出。
六、分支排序优化(贪心前置,优先搜索合法分支)
调整循环内元素遍历顺序,优先走更容易得到解的分支,提前找到答案后可直接终止搜索(适合只求单解场景)。 示例:括号生成优先递归左括号分支;求和题目优先遍历小数,更早触发剪枝。
七、记忆化/状态缓存(极少回溯场景,棋盘/路径类)
适用:棋盘回溯(N皇后、岛屿、单词搜索),缓存已访问坐标、状态,避免重复搜索同一子问题。 例:单词搜索用visited标记棋盘格子,不走重复坐标;N皇后用数组缓存列、斜线占用状态,O(1)判断能否放皇后。
八、全局提前终止(只需要任意一组解时)
如果题目只要求找到任意一条合法路径,不需要全部解,设置全局标记boolean found,找到解后每层递归直接return,立刻停止所有搜索:
boolean found = false;
void backtrack(...){
if(found) return; // 已经找到答案,直接返回
if(满足条件){
res.add(...);
found = true;
return;
}
...
}
优化优先级(面试做题顺序)
- 排序+剪枝(提升最大,必写)
- start下标缩小循环范围(组合题标配)
- 同层去重(数组含重复数字必写)
- StringBuilder替代String拼接(字符串回溯海量分支)
- 全局变量减少传参、迭代回溯防栈溢出(大数据场景)
- 记忆化状态缓存(棋盘、N皇后类)
配套你之前回溯专题的优化落地举例
- 39组合总和:排序+sum剪枝break + start缩小循环
- 40组合总和II:排序+同层i>start去重 + sum提前剪枝
- 22括号生成:合法性剪枝 + StringBuilder优化字符串
- 78子集:start下标缩小循环,减少分支
- 46全排列:visited标记,避免重复选取元素
- 17电话号码:无剪枝,可用StringBuilder减少字符串创建