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) {
vector<vector<int> > ret;
Helper(ret, num, );
return ret;
}
void Helper(vector<vector<int> >& ret, vector<int> num, int pos)
{
if(pos == num.size()-)
ret.push_back(num);
else
{
for(int i = pos; i < num.size(); i ++)
{//swap all the ints to the current position
swap(num[pos], num[i]);
Helper(ret, num, pos+);
swap(num[pos], num[i]);
}
}
}
};

【LeetCode】46. Permutations (2 solutions)-LMLPHP

解法二:just a joke

别忘了先排序,因为next_permutation是升序返回的。

class Solution
{
public:
vector<vector<int> > permute(vector<int> &num)
{
vector<vector<int> > result;
//sort first
//note that next_permutation is in ascending order
sort(num.begin(), num.end());
result.push_back(num);
while(next_permutation(num.begin(), num.end()))
{
result.push_back(num);
}
return result;
}
};

【LeetCode】46. Permutations (2 solutions)-LMLPHP

04-14 19:30