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

Pasted from <http://leetcode.com/onlinejudge>

Analysis:

Given [1,1,2], by normal permutations, we will have the following sequence:

1, 1, 2,

1, 2, 1,

1, 1, 2

1, 2, 1

2, 1, 1

2, 1, 1

We noticed that there is duplicate because the black "1" did the same routine as the red "1". So, if let the black "1" be able to be used only when the red "1" is being used, we can rule out the duplicate permutation. 

void permuteUniqueHelper(vector >& permutations, vector permutation, const vector &num, vector used) {
    if (permuations.size() == num.size())
        permutations.push_back(permutation);
    else
    {
        for (int i=0; i < num.size(); i++)
        {
            if (used[i] || (i > 0 && num[i] == num[i-1] && !used[i-1]))
                continue;
            used[i] = true;
            permutation.push_back(num[i]);
            permuteUniqueHelper(permutations, permutation, num, used);
            used[i] = false;
            permutation.pop_back();
        }  
    }      
}

vector > permuteUnique(vector &num) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    vector > permutations;
    vector permutation;
    vector used(num.size(), false);
    permuteUniqueHelper(permutations, permutation, num, used);
   
    return permutations;

}