「leetcode」46.全排列【回溯算法】详细图解！
最新回答
厌恶点
2026-04-03 07:55:47
全排列问题可以通过回溯算法高效解决。以下是详细图解和步骤说明：
核心思路全排列要求生成所有可能的顺序组合，例如输入 [1,2,3] 的输出包含 [1,2,3]、[1,3,2] 等。回溯法通过递归遍历所有可能的路径，并通过 标记已用元素 避免重复使用同一数字。
回溯三部曲1. 递归函数参数- 关键点：排列需记录已用元素（used数组），无需startIndex（因每次从头搜索）。
- 代码：vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, vector<bool>& used)
- 触发时机：当 path 长度等于输入数组长度时，说明找到一个排列。
- 代码：if (path.size() == nums.size()) { result.push_back(path); return;}
- 步骤：
遍历数组，跳过已用元素（used[i] == true）。
标记当前元素为已用，加入 path，递归进入下一层。
回溯：撤销选择（弹出 path 末尾元素，重置 used[i]）。
- 代码：for (int i = 0; i < nums.size(); i++) { if (used[i]) continue; used[i] = true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] = false;}
- 初始状态：path = []，used = [F, F, F]。
- 第一层递归：
选择 1：path = [1]，used = [T, F, F]。
进入第二层，选择 2：path = [1,2]，used = [T, T, F]。
进入第三层，选择 3：path = [1,2,3] → 触发终止条件，保存结果。
回溯：弹出 3，重置 used[2]；选择 3（第二层）：path = [1,3] → 继续递归生成 [1,3,2]。
- 重复上述过程，直到遍历所有分支，生成全部排列。
- 与组合/子集的区别：
排列需从头搜索（无startIndex）。
需 used 数组避免重复使用元素。
- 时间复杂度：O(n!)，因全排列数量为 n!。
- 空间复杂度：O(n)，递归栈深度与 path 长度相关。
- 含重复元素的全排列：需先排序，并在递归中跳过相同元素（参考 47.全排列 II）。
- 优化：可通过交换元素替代 used 数组（原地标记），减少空间占用。
通过回溯法，可以系统化地生成所有可能解，适用于排列、组合等搜索问题。
热门标签
