Permutations II

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

--------------------------------------- thinking ----------------------------------------------
http://decomplexify.blogspot.com/2014/05/permutations.html
None next Permutation method:
https://oj.leetcode.com/discuss/20598/accepted-backtracking-c-solution-by-using-map-28ms
http://www.programcreek.com/2013/02/leetcode-permutations-ii-java/
http://fisherlei.blogspot.com/2012/12/leetcode-permutations-ii.html
--------------------------------------- codes --------------------------------------------------
class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int>> result;
        vector<vector<int>> tmp;
        if (num.size() == 0) {
            return result;
        }
        if (num.size() == 1) {
            result.push_back(num);
            return result;
        }
        sort(num.begin(), num.end());
        result.push_back(num);
        while (nextPermute(num)) {
            result.push_back(num);
        }
        return result;
    }
    bool nextPermute(vector<int> &num) {
        //edge cases -> duplications
        //from right to left, find the first decreasing bit
        int i = num.size() - 2;
        while (i >= 0) {
            if (num[i] < num[i+1]) {
                break;
            }
            i--;
        }
        if (i == -1) {
            return false;
        }
        //from left to right, find the last bit that is bigger than num[i]
        int j = i+1;
        while (j < num.size()) {
            //because we have duplications, the comparison should have equal considered
            if (num[j] <= num[i]) {
                break;
            }
            j++;
        }
        j--;
     
        //swap num[i] & num[j]
        int tmp = num[i];
        num[i] = num[j];
        num[j] = tmp;
     
        //reverse (i+1, ..)
        int start = i+1;
        int end = num.size() - 1;
        while (start < end) {
            int tmp = num[start];
            num[start] = num[end];
            num[end] = tmp;
            start++;
            end--;
        }
        return true;
    }
};