permutations

Solution: Recursive:

class Solution {
public:
    //vector<vector<int> > answer;
    vector<vector<int> > permute(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > answer;
        int n = num.size();
        perm(num,n-1, 0,answer);
        return answer;
    }

    void perm(vector<int> &num, int n, int i, vector<vector<int> > &answer) {
        int j;
        if(n==i) {
            answer.push_back(num);
        } else {
            for(j = i; j <= n; j++) {
                swap(num[i], num[j]);
                perm(num,n,i+1, answer);
                swap(num[i], num[j]);
            }
        }
    }

    void swap (int &x, int &y) {
        int temp;
        temp = x;
        x = y;
        y = temp;
    }

};

=========== Second time ============
class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > sol;
        vector<int> single_vec;
        if (num.size() == 0)
            return sol;

        permute_helper(num, sol, single_vec, 0);
        return sol;
    }
    
    void permute_helper(vector<int> &num,
                        vector<vector<int> > &sol,
                        vector<int> &single_vec,
                        int index) {
        int size = num.size();
        int single_vec_size = single_vec.size();

        if (index == (size - 1)) {
            single_vec.push_back(num[index]);
            sol.push_back(single_vec);
            return;
        }
        for (int i = index; i < size; i++) {
            swap(num, i, index);
            single_vec.push_back(num[index]);
            permute_helper(num, sol, single_vec, index + 1);
            swap(num, index, i);
            single_vec.erase(single_vec.begin() + index, single_vec.end());
        }
        return;
    }
    
    void swap(vector<int> &num, int id1, int id2) {
        int temp = num[id1];
        num[id1] = num[id2];
        num[id2] = temp;
    }
};
===== Without additional vector =======
class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > sol;
        if (num.size() == 0)
            return sol;

        permute_helper(num, sol, 0);
        return sol;
    }
    
    void permute_helper(vector<int> &num,
                        vector<vector<int> > &sol,
                        int index) {
        int size = num.size();

        if (index == (size - 1)) {
            sol.push_back(num);
            return;
        }
        for (int i = index; i < size; i++) {
            swap(num, i, index);
            permute_helper(num, sol, index + 1);
            swap(num, index, i);
        }
        return;
    }
    
    void swap(vector<int> &num, int id1, int id2) {
        int temp = num[id1];
        num[id1] = num[id2];
        num[id2] = temp;
    }
};

==================================================

Iterative: (small judge)

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > sol;
     
        int size = num.size();
        if (size > 0) {
            sort(num.begin(), num.end());
            sol.push_back(num);
        } else {
            return sol;
        }
        int totalCount = fact(size);
        for (int count = 0; count < totalCount - 1; count++) {
            vector<int> single;
            int justSmallerIndex;
            for (int iter = size - 1; iter > 0; iter--) {
                justSmallerIndex = min(num, iter);
                if (justSmallerIndex != -1) {
                    swap(num[iter], num[justSmallerIndex]);
                    sort(num.begin() + justSmallerIndex + 1, num.end());
                    break;
                }
            }
            for (int i = 0; i < size; i++) {
                single.push_back(num[i]);
            }
            sol.push_back(single);
        }
        return sol;
    }
 
    int min(vector<int> & num, int index) {
        int justSmallerIndex = index - 1;
        int numberToCompared = num[index];
        for (int i = index - 1; i >= 0; i--)
            if (num[i] < numberToCompared)
                return i;
        return -1;
    }

    void swap(int &first, int &second) {
        int temp = first;
        first = second;
        second = temp;
    }
 
    int fact(int num) {
        if (num == 0 || num == 1)
            return 1;
        else
            return num * fact(num - 1);
    }
};