【leetcode】Permutations (middle)

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]);
}
}
};
上一篇:前端开发面试题JS


下一篇:c++primer复习(一)