在算法的世界里，我们常常会遇到这样一类问题：需要从众多可能的解中找到满足条件的答案，比如排列组合、子集选取、路径搜索等。如果用纯粹的暴力枚举，往往会因为时间复杂度太高而无法承受。而回溯法，正是一种在暴力枚举基础上优化的 “聪明策略”—— 它像走迷宫一样，一路探索，走不通就退回上一步换条路，大大减少了不必要的计算。
回溯法（Backtracking）是一种试探性的搜索算法，核心思想可以概括为：“走不通，就回头”。
它的本质是深度优先搜索（DFS） 的一种应用，通过递归的方式，一步步构建可能的解。在构建的过程中，每一步都会判断当前路径是否符合条件：如果符合条件，就继续向下探索；如果不符合条件，就回溯—— 撤销当前的选择，回到上一步，尝试其他可能的选择。
这种 “剪枝” 的操作，能避免对大量无效路径的遍历，从而降低时间复杂度。
举个生活中的例子：你要找一把钥匙，家里有客厅、卧室、厨房三个房间。你先搜客厅，没找到，就退回到门口（回溯），再去搜卧室；卧室没找到，再退回门口，去搜厨房 —— 这就是回溯的思路。如果不回溯，可能会在客厅反复找，或者漏掉其他房间。
要掌握回溯法，关键是理清三个核心要素：
- 路径：已经做出的选择，也就是当前构建的解的部分内容。
- 选择列表：当前可以选择的选项，也就是下一步能走的 “岔路”。
- 结束条件：到达什么状态时，就可以确定当前路径是一个完整的解（或者确定这条路走不通）。
回溯法的通用模板如下：
function backtrack(路径, 选择列表): if 满足结束条件: 将路径加入结果集 return for 选择 in 选择列表: 做选择（将选择加入路径） backtrack(路径, 新的选择列表) 撤销选择（将选择从路径中移除，回溯）这个模板是所有回溯问题的 “万能框架”，无论是排列、组合还是子集问题，都可以套用这个结构来解决。
光说理论太抽象，可以用全排列问题来实战一下 —— 给定一个不含重复数字的数组nums，返回其所有可能的全排列。
比如输入nums = [1,2,3]，输出应该是[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。
确定核心要素
- 路径：当前已经选好的数字列表，比如
[1]、[1,2]。 - 选择列表：当前还没被选过的数字，比如路径是
[1]时，选择列表是[2,3]。 - 结束条件：路径的长度等于数组的长度（所有数字都选完了）。
- 路径：当前已经选好的数字列表，比如
套用模板写代码（以 Java 为例）
import java.util.ArrayList; import java.util.List; public class Permutations { // 存储最终结果 List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { // 存储当前路径 List<Integer> path = new ArrayList<>(); // 标记数字是否被使用过 boolean[] used = new boolean[nums.length]; backtrack(nums, path, used); return res; } private void backtrack(int[] nums, List<Integer> path, boolean[] used) { // 结束条件：路径长度等于数组长度 if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; } // 遍历选择列表 for (int i = 0; i < nums.length; i++) { if (used[i]) { continue; // 跳过已使用的数字 } // 做选择 path.add(nums[i]); used[i] = true; // 递归探索下一层 backtrack(nums, path, used); // 撤销选择（回溯） path.remove(path.size() - 1); used[i] = false; } } public static void main(String[] args) { Permutations solution = new Permutations(); int[] nums = {1, 2, 3}; System.out.println(solution.permute(nums)); } }used数组的作用是标记哪些数字已经被选入路径，避免重复选择。每次递归时，先把当前数字加入路径，标记为已使用；递归结束后，再把数字从路径中移除，标记为未使用 —— 这就是回溯的关键操作。当路径长度等于数组长度时，就把路径的副本加入结果集（注意要 new 一个新的 ArrayList，否则会因为引用问题导致结果被覆盖）。
回溯法的效率高低，关键在于剪枝—— 在遍历选择列表时，提前排除那些不可能产生有效解的路径。比如在组合总和问题中，如果当前路径的和已经超过了目标值，就没必要继续往下探索了，直接返回即可。这种操作能大幅减少递归的次数，优化时间复杂度。
if (currentSum > target) { return; // 剪枝：和超过目标值，直接回溯 }剪枝没有固定的套路，需要根据具体问题的条件来设计，但核心思路都是 提前止损。
回溯法不是万能的，但在以下几类问题中，它是最优解或者常用解：排列 / 组合 / 子集问题：比如全排列、组合总和、子集生成等。棋盘问题：比如 N 皇后、数独求解。路径搜索问题：比如矩阵中的路径、单词搜索。括号生成问题：比如生成有效的括号组合。
回溯法的本质是 “深度优先搜索 + 剪枝”，它不像动态规划那样有很高的思维门槛，更多的是一种 “套路化” 的算法 —— 只要掌握了路径、选择列表、结束条件这三个核心要素，套用通用模板，再根据具体问题调整细节，就能解决大部分回溯类题目。学习回溯法的关键，不是死记硬背代码，而是理解“做选择 - 递归 - 撤销选择” 这个核心流程。
)
