回溯法详解：LeetCode 46. 全排列

一、 问题描述给定一个不含重复数字的数组nums返回其所有可能的全排列。你可以按任意顺序返回答案。示例输入nums [1,2,3]输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]二、 核心思路回溯 (Backtracking)全排列问题是回溯算法最经典的入门题。回溯算法的本质是决策树的深度优先遍历 (DFS)。我们可以将全排列问题具象化为有n个空位我们需要从左到右依次填入nums中的数字。每个数字只能用一次。1. 状态定义在遍历决策树的过程中我们需要维护以下几个关键状态路径 (Path)记录当前已经做出的选择即当前正在生成的排列。选择列表当前还可以做出的选择即数组中还未被使用的数字。结束条件到达决策树底层无法再做选择的条件。2. 关键难点如何记录“已使用”由于数组中的元素不能重复使用我们需要一个标记机制。最直接的方法是引入一个布尔数组usedused[i] true表示nums[i]已经在当前路径中被使用。used[i] false表示nums[i]尚未被使用可以加入当前路径。3. 回溯过程图解以nums [1, 2, 3]为例决策树的遍历过程如下第一层可以选择 1, 2, 3。第二层如果第一层选了 1第二层只能从 2, 3 中选。第三层如果前两层选了 1, 2第三层只能选 3。当路径长度达到 3 时记录当前路径并撤销上一步选择回溯返回上一层尝试其他分支。三、 代码实现 (C)基于上述思路我们可以写出非常标准的回溯代码模板class Solution { public: vectorvectorint permute(vectorint nums) { vectorvectorint result; vectorint path; vectorbool used(nums.size(), false); backtrack(nums, used, path, result); return result; } private: void backtrack(const vectorint nums, vectorbool used, vectorint path, vectorvectorint result) { // 1. 终止条件路径长度等于数组长度说明找到了一个全排列 if (path.size() nums.size()) { result.push_back(path); return; } // 2. 遍历选择列表 for (int i 0; i nums.size(); i) { // 排除不合法的选择当前数字已被使用 if (used[i]) continue; // 3. 做选择 used[i] true; path.push_back(nums[i]); // 4. 进入下一层决策树 backtrack(nums, used, path, result); // 5. 撤销选择 (回溯核心) path.pop_back(); used[i] false; } } };四、 复杂度分析时间复杂度O(n×n!)总共有 n! 种全排列。每种排列需要 O(n) 的时间将其从path复制到result中。递归树的节点总数约为 e×n!因此整体时间复杂度为 O(n×n!)。空间复杂度O(n)递归调用栈的深度最大为 n。used数组和path数组的空间开销均为 O(n)。注意返回结果result占用的空间不计入算法的辅助空间复杂度。五、 拓展与普适化回溯算法通用模板全排列问题揭示了回溯算法解决“组合/排列/子集”类问题的通用范式。我们可以将其抽象为以下伪代码模板result [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 新的选择列表) 撤销选择