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].

深搜DFS。注意参数需要传引用。

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int>> re;
        vector<int> thisRe;
        DFS(num, re, thisRe);
        return re;
    }
    void DFS(vector<int> &num, vector<vector<int>> &re, vector<int> &thisRe){
        if(num.size() == 0) {
            re.push_back(thisRe);
            return ;
        }
        int len = num.size();
        for(int i = 0; i < len; i++){
            int tmp = num[i];
            thisRe.push_back(tmp);
            num.erase(num.begin() + i);
            DFS(num, re, thisRe);
            num.insert(num.begin() + i, tmp);
            thisRe.pop_back();
        }
    }
};