首页 > 代码库 > Permutations
Permutations
Given a collection of numbers, return all possible permutations.
For example,[1,2,3]
have the following permutations:[1,2,3]
, [1,3,2]
, [2,1,3]
, [2,3,1]
, [3,1,2]
, and [3,2,1]
.
class Solution {
public:
vector<vector<int> > permute(vector<int> &num)
{
bool used[num.size()];
for(int i=0;i<num.size();i++)
used[i]=false;
vector<vector<int> > result;
vector<int> possible;
for(int i=0;i<num.size();i++)
possible.push_back(0);
gen(result,num,used,0,possible);
return result;
}
void gen(vector<vector<int> >& result,vector<int>& num,bool* used,int step,vector<int>& possible)
{
if(step==num.size())
{
result.push_back(possible);
return;
}
for(int i=0;i<num.size();i++)
if(!used[i])
{
used[i]=true;
possible[step]=num[i];
gen(result,num,used,step+1,possible);
used[i]=false;
}
}
};
public:
vector<vector<int> > permute(vector<int> &num)
{
bool used[num.size()];
for(int i=0;i<num.size();i++)
used[i]=false;
vector<vector<int> > result;
vector<int> possible;
for(int i=0;i<num.size();i++)
possible.push_back(0);
gen(result,num,used,0,possible);
return result;
}
void gen(vector<vector<int> >& result,vector<int>& num,bool* used,int step,vector<int>& possible)
{
if(step==num.size())
{
result.push_back(possible);
return;
}
for(int i=0;i<num.size();i++)
if(!used[i])
{
used[i]=true;
possible[step]=num[i];
gen(result,num,used,step+1,possible);
used[i]=false;
}
}
};
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。