全排列
进阶全排列展示了回溯里"做选择、递归、撤销选择"的完整节奏。
// 算法讲解
全排列
枚举所有排列，观察回溯的「选择-递归-撤销」节奏。
待机
速度 中
待机 ⌨1vector<int> path;
2vector<int> used;
3
4void dfs(const vector<int>& nums) {
5 if (path.size() == nums.size()) {
6 return;
7 }
8 for (int i = 0; i < (int)nums.size(); i++) {
9 if (used[i]) continue;
10 used[i] = 1;
11 path.push_back(nums[i]);
12 dfs(nums);
13 path.pop_back();
14 used[i] = 0;
15 }
16}
复杂度分析
时间 O(n * n!)
空间 O(n)
最优 O(1)
最坏 O(n * n!)
算法讲解
全排列的目标是枚举所有可能顺序，因此每一层递归都要决定当前位置放哪个还没用过的数。
回溯模板的关键就在于：选择一个候选，进入下一层，返回后把现场恢复。
如果这个"恢复现场"的动作漏掉了，后续分支就会带着脏状态继续跑，结果通常全错。
很多搜索题本质都可以看作"在状态树上枚举一条合法路径"。