Permutations

Q:

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

T:
Typical recursive application. For each permutation including the elements after the nth element, we can insert the nth element in each position to generate a permutation including the nth element.

A:

class Solution {
public:
    vector< vector< int > > ret;
    void generate(int n, vector& num) {
        if(n == num.size()-1) {
            vector< int > vec;
            vec.push_back(num[n]);
            ret.push_back(vec);
            return;
        }
        generate(n+1, num);
        int sz = ret.size();
        for(int i=0; i< sz; i++) {
            vector< int > vec = ret[i];
            ret[i].insert(ret[i].begin(), num[n]);
            for(int j=1; j<=vec.size(); j++) {
                vector< int > vec2 = vec;
                vec2.insert(vec2.begin() + j, num[n]);
                ret.push_back(vec2);
            }
        }
    }
    vector< vector< int > > permute(vector< int > &num) {
        generate(0, num);
        return ret;
    }
};