一、回溯法核心概念1.1 什么是回溯法回溯法Backtracking是一种基于深度优先搜索DFS的暴力搜索算法核心思想是在解决问题的过程中逐步构建解的路径当发现当前路径无法得到有效解时就 “回退” 到上一步重新选择其他路径继续探索。可以把回溯法理解为 “走迷宫”遇到死胡同就原路返回换一条路继续走直到找到出口或遍历完所有路径。1.2 回溯法的核心特征试探性每一步都尝试所有可能的选择不满足条件则回退剪枝在搜索过程中提前排除不可能的路径优化手段减少无效搜索递归实现回溯法通常用递归实现也可手动用栈实现递归的深度对应解的维度全局状态需要维护全局的 “路径” 和 “已选择” 状态回退时要恢复状态。1.3 回溯法解题框架万能模板回溯法的解题逻辑可以抽象为以下固定框架几乎所有回溯问题都能套用java运行// 全局变量存储最终结果 ListListInteger result new ArrayList(); // 全局变量存储当前路径 ListInteger 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特性回溯法普通 DFS核心目标寻找所有可行解 / 最优解遍历所有节点 / 判断可达性状态处理需维护并恢复路径状态仅标记访问状态剪枝核心优化手段可选非必须应用场景组合、排列、子集、分割等图遍历、连通性判断等二、力扣中低难度回溯实战题题目 1子集LeetCode 78中等题目描述给你一个整数数组nums数组中的元素互不相同。返回该数组所有可能的子集幂集。解集不能包含重复的子集。你可以按任意顺序返回解集。解题思路回溯核心子集问题是 “选或不选” 的问题每个元素有两种选择加入当前子集 或 不加入回溯框架应用终止条件遍历完所有元素时将当前路径子集加入结果选择列表当前位置之后的所有元素剪枝无需剪枝所有子集都有效选择 / 回溯加入当前元素 → 递归 → 移除当前元素。完整代码java运行import java.util.ArrayList; import java.util.List; class Solution { // 存储最终所有子集 private ListListInteger result new ArrayList(); // 存储当前子集路径 private ListInteger path new ArrayList(); public ListListInteger 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]); // 递归探索下一层从i1开始避免重复选择同一元素 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。测试用例输入输出部分解释[1,2,3][], [1], [2], [3], [1,2]所有子集共 8 个包含空集题目 2组合LeetCode 77中等题目描述给定两个整数n和k返回范围[1, n]中所有可能的k个数的组合。你可以按任何顺序返回答案。解题思路回溯核心从 1~n 中选择 k 个数不考虑顺序需限制路径长度为 k回溯框架应用终止条件路径长度等于 k 时将路径加入结果选择列表当前位置之后的所有数剪枝若剩余可选数不足 k - path.size ()直接跳过优化选择 / 回溯加入当前数 → 递归 → 移除当前数。完整代码java运行import java.util.ArrayList; import java.util.List; class Solution { private ListListInteger result new ArrayList(); private ListInteger path new ArrayList(); public ListListInteger 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); // 递归下一个数从i1开始 backtrack(n, k, i 1); // 回溯 path.remove(path.size() - 1); } } }代码说明剪枝优化i n - (k - path.size()) 1是核心优化例如 n5、k3当 path.size ()1 时剩余需要选 2 个数因此 i 最大只能到 45-21若 i5 则无法选够 2 个数直接跳过终止条件只有路径长度等于 k 时才是有效组合加入结果时间复杂度O (C (n,k)×k)C (n,k) 是组合数每个组合复制需要 O (k) 时间空间复杂度O (k)递归深度最多为 k。测试用例输入输出解释n4,k2[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]1