[LeetCode] Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

Similar with Permutations I, next_permutation can be used to iterate all the permutations. A recursive solution is given as well. 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(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:
    bool hasDuplication(vector<int> &num, 
                        int start, int end)
    {
        for(int i=start; i<end; i++)
        {
            if(num[i] == num[end]) return true;
        }
        return false;
    }
    
    void permutation(vector<int> &num, 
                    int start, 
                    int end, 
                    vector<vector<int>> &res)
    {
        if(start == end)
        {
            res.push_back(num);
            return;
        }
        for(int i=start; i<=end; i++)
        {
            if(hasDuplication(num, start, i)) continue;
            swap(num[start], num[i]);
            permutation(num, start+1, end, res);
            swap(num[start], num[i]);
        }
    }

    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int>> res;
        permutation(num, 0, num.size()-1, res);
        return res;
    }
};