1. 题目来源
链接：
46. 全排列
必看，必刷，dfs 经典：
-
[Mdfs] lc39. 组合总和(dfs+经典)
-
[Mdfs] lc40. 组合总和 II(dfs+经典)
-
[Mdfs] lc46. 全排列(dfs+经典)
-
[Mdfs] lc47. 全排列 II(dfs搜索顺序+去重处理+知识理解+经典)
-
[Mdfs] lc77. 组合(组合类型枚举+题目总结+经典)
-
[Mdfs] lc78. 子集(二进制枚举+排列类型枚举+经典)
-
[Mdfs] lc90. 子集 II(组合类型枚举+多重背包+去重经典)
2. 题目解析
dfs
模板题没啥好说的。
思路：
- 按排列的位来枚举填哪些数
-
dfs
维护一个
u
，表示当前填到哪一位了，维护一个数组
path
存当前答案，再维护一个
st
判重数组判定哪些数字已经填过了。 -
当
u == nums.size()
则表示当前的
path
已经填满了，扎到一个排列，将其添加到答案即可
时间复杂度：
O
(
n
∗
n
!
)
O(n*n!)
O
(
n
∗
n
!
)
。不会分析，可见官方题解…
空间复杂度：
O
(
n
)
O(n)
O
(
n
)
代码：
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
vector<bool> st;
vector<vector<int>> permute(vector<int>& nums) {
st = vector<bool>(nums.size());
dfs(nums, 0);
return ans;
}
void dfs(vector<int> &nums, int u) {
if (u == nums.size()) {
ans.push_back(path);
return ;
}
for (int i = 0; i < nums.size(); i ++ ) {
if (!st[i]) {
st[i] = true;
path.push_back(nums[i]);
dfs(nums, u + 1);
st[i] = false;
path.pop_back();
}
}
}
};