Description
Given a list of numbers, return all possible permutations.
Example
For nums = [1,2,3], the permutations are:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
Challenge
Do it without recursion.
1
2 1 ---> 基于[1]位置0插入2
1 2 ---> 基于[1]位置1插入2,并移除[1]
3 2 1 ---> 基于[2 1]位置0插入3
...
2 1 3 ---> 基于[2 1]位置2插入3,并移除[2 1]
3 1 2 ---> 基于[1 2]位置0插入3
...
1 2 3 ---> 基于[1 2]位置2插入3,并移除[1 2]
class Solution {
public:
void mypermute(vector<int> src, int i, vector<vector<int> > &dst, int offset) {
if (i >= src.size()) return;
//init
if (i == 0) {
vector<int> unit(1, src[i]);
dst.insert(dst.end(), 1, unit);
mypermute(src, i+1, dst, offset);
return;
}
//insert target to dst in offset.
vector<int>tmp(dst[0]);
tmp.insert(tmp.begin()+offset, 1, src[i]);
dst.insert(dst.end(), 1, tmp);
//if offset is end, remove current and start next
offset++;
if (offset > i) {
dst.erase(dst.begin(), dst.begin()+1);
offset = 0;
}
//next target
if (dst[0].size() == i+1) {
i++;
}
mypermute(src, i, dst, offset);
}
/*
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector<vector<int>> permute(vector<int> &nums) {
// write your code here
vector<vector<int>> ret;
if (nums.size() == 0) {
vector<int>empty;
ret.insert(ret.end(), 1, empty);
return ret;
}
mypermute(nums, 0, ret, 0);
return ret;
}
};