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].
求没有重复数字的全排列
思路：用的标准回溯法，一次AC
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int>> ans;
if(num.empty())
{
return ans;
}
vector<int> X(num.size());
vector<vector<int>> S(num.size());
int k = ;
S[k] = num;
while(k >= )
{
while(!S[k].empty())
{
X[k] = S[k].back();
S[k].pop_back();
if(k < num.size() - )
{
k++;
S[k] = num;
for(int i = ; i < k; i++)
{
vector<int>::iterator it;
if((it = find(S[k].begin(), S[k].end(), X[i])) != S[k].end())
{
S[k].erase(it);
}
}
}
else
{
ans.push_back(X);
}
}
k--;
}
return ans;
}
};
网上也有用递归的
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > result;
permuteRecursive(num, , result);
return result;
}
// permute num[begin..end]
// invariant: num[0..begin-1] have been fixed/permuted
void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result) {
if (begin >= num.size()) {
// one permutation instance
result.push_back(num);
return;
}
for (int i = begin; i < num.size(); i++) {
swap(num[begin], num[i]);
permuteRecursive(num, begin + , result);
// reset
swap(num[begin], num[i]);
}
}
};