题目描述
给定一个没有重复数字的序列,返回其所有可能的全排列。
样例
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
算法1
(DFS)
枚举每个位置放不同的数字。
以位置的顺序为依据,vis来记录 数字 的使用情况。
C++ 代码
class Solution {
public:
vector<vector<int>> res;
int n;
vector<vector<int>> permute(vector<int>& nums) {
n = nums.size();
vector<bool> vis(n,0); //记录 数字 的使用情况
vector<int> path(n);
dfs(nums, path, vis, 0);
return res;
}
void dfs(vector<int> &nums, vector<int> &path, vector<bool> &vis, int u){
if(u == n){ //所有的数字已使用
res.push_back(path);
return;
}
for(int i = 0; i < n;i++) //遍历每一个数字
if(!vis[i]){ //该数字没有使用过
vis[i] = true;
path[u] = nums[i]; //将未使用过的数字放到指定位置
dfs(nums, path, vis, u + 1); //指定下一个位置
vis[i] = false; // 恢复现场
//path 不用恢复,每次会被覆盖。
}
}
};
总结:非字典序
算法2
(DFS)
枚举每个数字放在不同的位置。
以每个数字的顺序为依据,vis来记录 位置 的使用情况。
时间复杂度
C++ 代码
class Solution {
public:
vector<vector<int>> ans;
int n;
vector<vector<int>> permute(vector<int>& nums) {
n = nums.size();
vector<bool> vis(n,0); //记录每个位置的使用情况
vector<int> path(n);
dfs(nums, path, vis, 0);
return ans;
}
void dfs(vector<int>& nums, vector<int> &path, vector<bool> &vis, int u){
if(u == n){ // 所有的位置都已使用
ans.push_back(path);
return;
}
for(int i = 0; i < n; i++) // 遍历每一个位置
if(!vis[i]){ //该位置未使用
vis[i] = true;
path[i] = nums[u]; //将指定数字放入未使用的位置
dfs(nums, path, vis, u + 1); // 指定下一个数字
vis[i] = false; //恢复现场
//path 不用恢复,每次会被覆盖。
}
}
};
总结:字典序
这两段代码只有两个字母之差:
path[u] = nums[i]; //将未使用过的数字放到指定位置
path[i] = nums[u]; //将指定数字放入未使用的位置