原题链接:Leecode 46. 全排列
解法一:
class Solution {
public:
vector<vector<int>> res;
vector<int> tmp;
map<int,int> m;
void dfs(int n,vector<int>& nums)
{
if(n==nums.size())
{
res.push_back(tmp);
return ;
}
for(int i=0;i<nums.size();i++)
{
if(!m[nums[i]])
{
tmp.push_back(nums[i]);
m[nums[i]]=1;
dfs(n+1,nums);
tmp.pop_back();
m[nums[i]]=0;
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
int n=nums.size();
dfs(0,nums);
return res;
}
};
解法二:swap
class Solution {
public:
vector<vector<int>> res;
void dfs(int n,vector<int>& nums)
{
if(n==nums.size())
{
res.push_back(nums);
return ;
}
for(int i=n;i<nums.size();i++)
{
swap(nums[i],nums[n]);
dfs(n+1,nums);
swap(nums[i],nums[n]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
dfs(0,nums);
return res;
}
};