LeetCode 46. 全排列 | C 回溯算法题解 题目描述题目级别中等给定一个不含重复数字的数组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)配合回溯的思想路径 (path)用来记录当前已经做出的选择例如当前已经选了[1, 2]。选择列表当前还可以选哪些数字。我们通过一个布尔数组st(state/visited) 来记录哪些数字已经被放进path中了。结束条件当path里的数字个数等于nums的长度时说明我们完成了一次排列把它加入结果集res中。灵魂操作撤销选择 (Backtracking)回溯算法最核心的一步在于“撤销”。当我们顺着一条路走到黑找到一个排列或者发现此路不通时我们需要退回到上一个岔路口去尝试其他的选择。在代码中表现为前进path.push_back(nums[i]); st[i] true;(把数字加进来标记为已用)递归dfs(nums, u 1);(继续去填下一个空位)后退撤销st[i] false; path.pop_back();(把刚才加进来的数字拿出来标记为未用把位置腾出来给别的数字尝试) C 代码实现classSolution{public:intn;vectorvectorintres;// 存储所有全排列的结果vectorintpath;// 存储当前正在构建的排列路径vectorboolst;// 状态数组记录数字是否已经被使用vectorvectorintpermute(vectorintnums){nnums.size();stvectorbool(n,false);// 初始化状态数组// 从第 0 个位置开始深度优先搜索dfs(nums,0);returnres;}// u 表示当前正在填第几个空位voiddfs(vectorintnums,intu){// 1. 结束条件所有空位都填满了if(un){res.push_back(path);// 将构建好的排列加入结果集return;}// 2. 遍历所有可能的选择for(inti0;in;i){// 如果 nums[i] 还没有被当前路径使用过if(!st[i]){// --- 做选择 ---path.push_back(nums[i]);st[i]true;// --- 递归进入下一层 ---dfs(nums,u1);// --- 撤销选择 (回溯) ---st[i]false;path.pop_back();}}}};