一、回溯法核心概念

1.1 什么是回溯法？

回溯法（Backtracking）是一种基于深度优先搜索（DFS）的暴力搜索算法，核心思想是：在解决问题的过程中，逐步构建解的路径，当发现当前路径无法得到有效解时，就 “回退” 到上一步，重新选择其他路径继续探索。

可以把回溯法理解为 “走迷宫”：遇到死胡同就原路返回，换一条路继续走，直到找到出口或遍历完所有路径。

1.2 回溯法的核心特征

• 试探性：每一步都尝试所有可能的选择，不满足条件则回退；
• 剪枝：在搜索过程中提前排除不可能的路径（优化手段），减少无效搜索；
• 递归实现：回溯法通常用递归实现（也可手动用栈实现），递归的深度对应解的维度；
• 全局状态：需要维护全局的 “路径” 和 “已选择” 状态，回退时要恢复状态。

1.3 回溯法解题框架（万能模板）

回溯法的解题逻辑可以抽象为以下固定框架，几乎所有回溯问题都能套用：

java

运行

// 全局变量：存储最终结果 List<List<Integer>> result = new ArrayList<>(); // 全局变量：存储当前路径 List<Integer> path = new ArrayList<>(); public void backtrack(选择列表, 路径, 已选状态) { // 1. 终止条件：路径满足要求，将路径加入结果集 if (终止条件) { result.add(new ArrayList<>(path)); // 注意：要新建列表，避免引用问题 return; } // 2. 遍历所有可选选项 for (选择 : 选择列表) { // 3. 剪枝：排除无效选择（可选，优化性能） if (选择无效) { continue; } // 4. 做出选择：将当前选择加入路径，标记已选 path.add(选择); 标记已选状态; // 5. 递归探索下一层 backtrack(选择列表, 路径, 已选状态); // 6. 回溯：撤销选择，恢复状态 path.remove(path.size() - 1); 恢复已选状态; } }

1.4 回溯法 vs 普通 DFS

二、力扣中低难度回溯实战题

题目 1：子集（LeetCode 78，中等）

题目描述

给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。

解题思路（回溯）

• 核心：子集问题是 “选或不选” 的问题，每个元素有两种选择：加入当前子集 或 不加入；
• 回溯框架应用：
  1. 终止条件：遍历完所有元素时，将当前路径（子集）加入结果；
  2. 选择列表：当前位置之后的所有元素；
  3. 剪枝：无需剪枝（所有子集都有效）；
  4. 选择 / 回溯：加入当前元素 → 递归 → 移除当前元素。

完整代码

java

运行

import java.util.ArrayList; import java.util.List; class Solution { // 存储最终所有子集 private List<List<Integer>> result = new ArrayList<>(); // 存储当前子集路径 private List<Integer> path = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) { if (nums == null) { return result; } // 从索引0开始回溯 backtrack(nums, 0); return result; } private void backtrack(int[] nums, int start) { // 终止条件：每一步的路径都是一个有效子集，直接加入结果（无需等遍历完所有元素） result.add(new ArrayList<>(path)); // 遍历当前可选的元素（从start开始，避免重复子集） for (int i = start; i < nums.length; i++) { // 做出选择：将nums[i]加入当前子集 path.add(nums[i]); // 递归探索下一层（从i+1开始，避免重复选择同一元素） backtrack(nums, i + 1); // 回溯：撤销选择，移除nums[i] path.remove(path.size() - 1); } } }

代码说明

• 终止条件特殊：子集问题中，每一步的路径都是一个有效子集，因此进入递归就先将路径加入结果，无需等遍历完所有元素；
• start参数的作用：限制选择列表的起始位置，避免生成重复子集（如 [1,2] 和 [2,1] 视为同一子集）；
• 时间复杂度：O (n×2ⁿ)（n 为数组长度，每个元素有选 / 不选两种可能，共 2ⁿ个子集，每个子集复制需要 O (n) 时间）；
• 空间复杂度：O (n)（递归深度最多为 n，路径列表的长度最多为 n）。

测试用例

题目 2：组合（LeetCode 77，中等）

题目描述

给定两个整数n和k，返回范围[1, n]中所有可能的k个数的组合。你可以按任何顺序返回答案。

解题思路（回溯）

• 核心：从 1~n 中选择 k 个数，不考虑顺序，需限制路径长度为 k；
• 回溯框架应用：
  1. 终止条件：路径长度等于 k 时，将路径加入结果；
  2. 选择列表：当前位置之后的所有数；
  3. 剪枝：若剩余可选数不足 k - path.size ()，直接跳过（优化）；
  4. 选择 / 回溯：加入当前数 → 递归 → 移除当前数。

完整代码

java

运行

import java.util.ArrayList; import java.util.List; class Solution { private List<List<Integer>> result = new ArrayList<>(); private List<Integer> path = new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { backtrack(n, k, 1); return result; } private void backtrack(int n, int k, int start) { // 终止条件：路径长度等于k，找到有效组合 if (path.size() == k) { result.add(new ArrayList<>(path)); return; } // 遍历可选数，剪枝：剩余数 = n - i + 1，需要满足 剩余数 >= k - path.size() // 即 i <= n - (k - path.size()) + 1 for (int i = start; i <= n - (k - path.size()) + 1; i++) { // 做出选择 path.add(i); // 递归：下一个数从i+1开始 backtrack(n, k, i + 1); // 回溯 path.remove(path.size() - 1); } } }

代码说明

• 剪枝优化：i <= n - (k - path.size()) + 1是核心优化，例如 n=5、k=3，当 path.size ()=1 时，剩余需要选 2 个数，因此 i 最大只能到 4（5-2+1），若 i=5 则无法选够 2 个数，直接跳过；
• 终止条件：只有路径长度等于 k 时，才是有效组合，加入结果；
• 时间复杂度：O (C (n,k)×k)（C (n,k) 是组合数，每个组合复制需要 O (k) 时间）；
• 空间复杂度：O (k)（递归深度最多为 k）。

测试用例