Leetcode: permutations

今天晚上再攻下一道题，求一个数组的所有排列，C++中有专门的函数next_permutation和prev_permutation,但是按照题目要求要自己写一个生成排列的函数。

代码思路很清晰，每次从nums中取出一个数，添加到已有的排列中，比如现在的ans有一个vector，接下来添加2，2可以加到1后面，也可以加到1前面。数字3的添加也是类似的，如下图。

image.png

代码如下

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        ans.push_back(vector<int>());
        for(auto it_nums = nums.begin(); it_nums != nums.end(); it_nums++) {
            int s = ans.size();
            for(int i = 0; i < s; i++){
                vector<int> tmp = ans[i];
                for(int j = 0; j <= tmp.size(); j++){
                    tmp.insert(tmp.begin()+j, *it_nums);
                    ans.push_back(tmp);
                    tmp.erase(tmp.begin()+j);
                }
            }
            ans.erase(ans.begin(), ans.begin()+s);
        }
        return ans;
    }
};

中间卡在了vector的insert和erase的相关问题，因为insert和erase之后原来的iterator可能会失效，所以需要注意一下这个问题。解决方法可以用一个vct.begin()+i来指向原来的元素，这样表达也会更清晰。