← 返回学习路线

SYSTEM

算法完整专题笔记:回溯(DFS)专项

算法
src/content/notes/algorithm/回溯.md

统一格式:题号+题目信息 → 题意简述 → 核心思路 → Java完整AC代码 → 通用模板 → 手动模拟要点 → 复杂度 → 总结&易错点 收录全部高频6道经典回溯题: 78.子集、46.全排列、39.组合总和、40.组合总和II、17.电话号码字母组合、22.括号生成

前置回溯基础概念

  1. 回溯 = 深度优先DFS,暴力枚举所有合法解,通过剪枝减少无效搜索
  2. 两大核心变量:
    • path:临时保存当前搜索路径,递归结束必须撤销(回溯恢复现场)
    • res:全局结果集合,存所有合法完整解
  3. 两大收集规则:
    • 子集类:每层递归都收集path(所有路径都是合法子集)
    • 组合/排列/括号:仅满足终止条件时收集(完整路径才合法)
  4. 三种控制不重复方案:
    • 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保证只向后遍历,无重复组合。

核心思路

  1. 递归参数start:只能从start下标向后选,避免乱序重复
  2. 进入递归立刻拷贝path加入结果(每层都收集)
  3. 循环选取当前i位置元素,递归i+1(每个元素只能选一次)
  4. 递归返回后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]

  1. start=0,path=[] → 存入[]

    • i=0,path=[1] → 存入[1]

      ,递归start=1

      • i=1,path=[1,2] → 存入[1,2],返回撤销2
    • 撤销1,i=1,path=[2] → 存入[2] 结果:[], [1], [1,2], [2]

复杂度

时间:O(n\cdot2^n),共2^n个子集,每个子集拷贝(O(n)) 空间:(O(n)),递归栈深度等于数组长度

易错点

  1. 必须new ArrayList<>(path),直接add(path)会引用覆盖
  2. 递归参数i+1,不可写i,否则元素重复选取
  3. 每层递归第一行收集结果,不是循环结束才收集

例题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长度等于数组长度时收集结果。

核心思路

  1. visited[]标记下标,true代表已选,循环跳过已访问元素
  2. 终止条件:path.size() == nums.length,收集完整排列
  3. 循环从i=0开始遍历全部元素(可以回头选前面数字)
  4. 选当前元素标记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]

  1. 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]存入结果

复杂度

时间:O(n\cdot n!),n!种排列,每种拷贝(O(n)) 空间:(O(n)),递归栈+visited数组

易错点

  1. 循环i从0开始,不用start,和子集区分开
  2. 回溯必须同时撤销path和visited标记,缺一不可
  3. 仅叶子节点收集结果,不要每层收集

例题3 LC39 组合总和

题目信息

无重复元素数组candidates,目标target;同一数字可无限次选取,返回和为target的不重复组合。 示例:candidates=[2,3,6,7], target=7,输出[[2,2,3],[7]]

题意简述

组合不区分顺序,不能出现[2,3] [3,2];使用start保证只向后选;递归传i而非i+1,允许重复选取当前数字。

核心思路

  1. start控制只向后遍历,避免重复组合
  2. sum记录当前路径和,sum>target直接剪枝返回
  3. sum==target收集结果
  4. 递归参数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)

易错点

  1. 递归传i,不是i+1,i+1则每个元素只能选一次(变成40题逻辑)
  2. start不能从0开始循环,否则生成乱序重复组合
  3. 提前剪枝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. 数组存在重复数字,同层循环去重防止重复组合。

核心思路

  1. 先排序,将相同数字聚拢,用于同层去重
  2. 循环判断:i>start && candidates[i]==candidates[i-1],同层重复直接跳过
  3. 递归参数i+1,每个元素只能选取一次
  4. 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)

易错点

  1. 必须先排序,否则同层去重失效
  2. 去重条件是i>start而非i>0,否则会删掉[1,1,6]这类合法含重复元素的组合
  3. 递归参数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。

核心思路

  1. 建立数字→字母映射数组
  2. index标记当前处理到第几个数字,终止条件index等于字符串长度
  3. 遍历当前数字所有对应字母,拼接字符串递归index+1
  4. 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))),递归栈深度等于数字长度

易错点

  1. 输入空字符串直接返回空列表,不能返回[""]
  2. index是数字下标,不要混淆字母循环下标
  3. 字符串拼接无需手动回溯撤销

例题6 LC22 括号生成

题目信息

n对括号,生成全部有效括号组合;有效规则:任意前缀左括号≥右括号,总左右括号数量相等。 示例:n=3,输出["((()))","(()())","(())()","()(())","()()()"]

题意简述

每层仅两种选择:加( 或加),带合法性剪枝;用open/close记录已使用左右括号数量。

核心思路

  1. open:已使用左括号,open < n 才能新增左括号
  2. close:已使用右括号,close < open 才能新增右括号(保证前缀合法)
  3. 终止条件:open == n && close == n,收集字符串
  4. 字符串拼接无需手动回溯撤销

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)

易错点

  1. 右括号条件不能写成close < n,必须close < open,否则产生非法括号
  2. 优先递归左括号分支,减少无效搜索
  3. 字符串自动拼接,不用手动删除字符

📊回溯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计数

回溯通用踩坑总览

  1. path引用陷阱:List类型path必须new ArrayList<>(path)拷贝存入结果,String拼接无此问题
  2. 回溯恢复现场:List添加元素后必须remove最后一位;visited标记必须递归返回后重置false
  3. 组合vs排列:组合用start不回头;排列用visited从头遍历
  4. 重复数组去重:40题必须排序+同层i>start判断,不能仅i>0
  5. 可重复选取:39递归传i;不可重复统一传i+1
  6. 剪枝优先: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;
    }
    ...
}

优化优先级(面试做题顺序)

  1. 排序+剪枝(提升最大,必写)
  2. start下标缩小循环范围(组合题标配)
  3. 同层去重(数组含重复数字必写)
  4. StringBuilder替代String拼接(字符串回溯海量分支)
  5. 全局变量减少传参、迭代回溯防栈溢出(大数据场景)
  6. 记忆化状态缓存(棋盘、N皇后类)

配套你之前回溯专题的优化落地举例

  1. 39组合总和:排序+sum剪枝break + start缩小循环
  2. 40组合总和II:排序+同层i>start去重 + sum提前剪枝
  3. 22括号生成:合法性剪枝 + StringBuilder优化字符串
  4. 78子集:start下标缩小循环,减少分支
  5. 46全排列:visited标记,避免重复选取元素
  6. 17电话号码:无剪枝,可用StringBuilder减少字符串创建