[LeetCode]—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].
解法一：使用STL中next_permutations函数，如果需要自己实现见：[LeetCode]—Next Permutation (全排列字典序)
解法二：采用DFS深搜的办法，并用一个数组标记该元素是否被访问过。
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > res;
vector<int> cur;
int count;
int n=num.size();
if(n<=1){
res.push_back(num);
return res;
}
int *bit=new int[n]; //表示该元素是否被访问过
memset(bit,0,sizeof(int)*n);
DFS(res,cur,num,0,bit);
return res;
}
private:
void DFS(vector<vector<int> > &res,vector<int> &cur,vector<int> &num,int count,int *bit){
int n=num.size();
if(count==n){
res.push_back(cur);
return;
}
for(int i=0;i<n;i++){
if(!bit[i]){
cur.push_back(num[i]);
bit[i]=1;
DFS(res,cur,num,count+1,bit);
bit[i]=0;
cur.pop_back();
}
}
}
};