[LeetCode] Permutations I

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

Simple non-recursive solution:

class Solution {
public:    
    vector<vector<int> > permute(vector<int> &num) {
        
        vector<vector<int>> res;
        sort(num.begin(),num.end());
        res.push_back(num);
        
        while ( next_permutation(num.begin(),num.end()))
        {
            res.push_back(num);
        } 

        return res;
    }
};

Use the implementation of next_permutation:

class Solution {
public:    
    vector<vector<int> > permute(vector<int> &num) {
        
        vector<vector<int>> res;
        sort(num.begin(),num.end());
        res.push_back(num);
        
        auto s = num.begin();
        auto e = num.end();
        auto i = e - 1;

        while(true && i != s)
        {
            auto j = i--;
            if(*i < *j)
            {
                auto k = e;
                while(*i >= *--k);
                
                iter_swap(i, k);
                reverse(j, e);
                res.push_back(num);
                i = e - 1;
            }
        }
        
        return res;
    }
};

Recursive solution:

class Solution {
public:

    void helper(vector<int>& stack, vector<int>& visited, 
                vector<int> &num, vector<vector<int>> &res)
    {
        int size = num.size();

        if(stack.size() == size)
        {
            res.push_back(stack);
            return;
        }
        
        for(int i=0;i<size;i++)
        {
            if(visited[i] == 0)
            {
                stack.push_back(num[i]);
                visited[i] = 1;
                helper(stack, visited, num, res);
                stack.pop_back();
                visited[i] = 0;
            }
        }

    }
    vector<vector<int> > permute(vector<int> &num) {
        
        vector<int> stack;
        vector<vector<int>> res;
        vector<int> visited (num.size(), 0);
        helper(stack,visited, num, res);
        return res;
    }

};