题目
思路
经典的排列问题,它主要借助递归函数去搜索。搜索的过程,类似于在一棵多叉树上进行。当遇到叶子节点时,即找到了一条合法的搜索路径。此时,需要跳出递归函数(栈),返回到上一层(即回溯的特性),进行搜索另一条分支路径,直到全部搜索完毕。
代码
class Solution {
public:
void dfs(vector<int>& nums, vector<int>& vis, vector<vector<int>>& rs, vector<int>& r) {
if (r.size() == nums.size()) {
rs.push_back(r);
return;
}
for (int i=0;i<nums.size();++i) {
if (vis[i]) continue;
vis[i]=1;
r.push_back(nums[i]);
dfs(nums,vis,rs,r);
r.pop_back();
vis[i]=0;
}
}
vector<vector<int>> permute(vector<int>& nums) {
int n=nums.size();
vector<int> vis(n,0);
vector<vector<int>> rs;
vector<int> r;
dfs(nums, vis, rs, r);
return rs;
}
};
复杂度分析
- Time:O(n * n!) n for nums.length,dfs 共有 n 层,第一层的合法选择是n,第二层的合法选择是 n – 1,…,第 n 层的合法选择是 1,故有 n! 级别次 dfs 函数的调用。可知,其方案数是 n!。每一种方案都需要将结果集 r 追加到 rs中,其复杂度是 O(n),故总体复杂度为O(n * n!)
- Space: O(n) 递归调用(栈)的深度
欢迎分享,引用。若转载,请联系我,谢谢配合。 本文地址:https://qoogle.top/xiaoxu-tutorial-leetcode-46-permutation/
2articles
[…] 小旭讲解 LeetCode 46. 全排列 […]