AcWing 51. 数字排列
原题链接
中等
作者:
术
,
2020-12-25 19:49:08
,
所有人可见
,
阅读 335
//i表示 新数组 第 i 个坑
//和上一个n排列不同,这个是以新数组 第几个坑 为树的结点(即把第一个值放入第几个坑)
//,上一个是以原数组 第几个的值 为结点
/*
1->指把第一个值放入第一个坑
2 3->指把第2个值放入第三个坑
3 2
*/
> class Solution
{
public:
vector<vector<int>> vv;
//int st[1005];有重复的数,不能用数组 用state
vector<int> v;
vector<vector<int>> permutation(vector<int>& nums)
{
v.resize(nums.size());//将v设为nums长度
sort(nums.begin(),nums.end());
//memset(st,0,sizeof(st));
dfs(nums,0,0,0);
return vv;
}
void dfs(vector<int>& nums,int u,int start,int state){
if(u==(int)nums.size()){
vv.push_back(v);
return;
}
if(!u||nums[u]!=nums[u-1]) start=0;
for(int i=start;i<(int)nums.size();i++){
if(!(state>>i&1)){
v[i]=nums[u];
dfs(nums,u+1,i+1,state+(1<<i));
}
}
}
};