时间复杂度
n*n!
递归层数:∑ k=1..n P(n,k) 次,调用递归 n次。
C++ 代码
class Solution {
public:
vector<vector<int>> output;
vector<int> temp;
vector<bool> flags;
vector<int> tmp;
vector<vector<int>> permute(vector<int>& nums) {
if(nums.empty()) return output;
flags.resize(nums.size(), false);
// dfs1(nums, 0);
tmp.resize(nums.size());
dfs2(nums, 0);
sort(output.begin(), output.end());
return output;
}
void dfs1(vector<int>& nums, int idx){
if(idx == nums.size()){
output.emplace_back(temp);
return;
}
// 枚举每个位置(idx),从0往后开始枚举放哪个数,flags[i]=true表示这个数放过了
for(int i = 0; i < nums.size(); i++){
if(flags[i] == false){
temp.emplace_back(nums[i]);
flags[i] = true;
dfs1(nums, idx+1);
temp.pop_back();
flags[i] = false;
}
}
}
void dfs2(vector<int>& nums, int n){
if(n == nums.size()){
output.emplace_back(tmp);
return;
}
//枚举每个数nums[n],放在那个位置,flags[i]=true表示这个位置有数
for(int i = 0; i < nums.size(); i++){
if(flags[i] == false){
tmp[i] = nums[n];
flags[i] = true;
dfs2(nums, n+1);
flags[i] = false;
}
}
}
};
//还有一种剑指offer里面的解法,基于交换:
class Solution {
public:
vector<vector<int>> output;
void dfs(vector<int>& nums, int k){
if(k == nums.size()) {
output.emplace_back(nums);
return;
}
for(int i = k; i < nums.size(); i++){
swap(nums[i], nums[k]);
dfs(nums, k+1);
swap(nums[i], nums[k]);
}
return;
}
vector<vector<int>> permute(vector<int>& nums) {
if(nums.empty()) return output;
dfs(nums, 0);
sort(output.begin(), output.end());
return output;
}
};
纠正一下,第一第二种写法时间复杂度应该是n*n^n