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;
        }
};