2
$\begingroup$

Please tell me why the expression i>0 && nums[i] == nums[i-1] && !used[i-1] works on getting unique permutations. And what is the math behind it?
The problem is as follows:
Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Here is the code:

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {   
        vector<vector<int>> result; 
        vector<int> temp;
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtrack(nums, temp, result, used);
        return result;        
    }
    
    void backtrack(vector<int>& nums, vector<int>& temp, vector<vector<int>>& result, vector<bool>& used){
        
        if(temp.size() == nums.size()){
            result.emplace_back(temp);
        }else{
            
            for(int i=0; i<nums.size(); i++){
                if(used[i] || i>0 && nums[i] == nums[i-1] && !used[i-1]) continue; 
                used[i] = true;
                temp.push_back(nums[i]);
                backtrack(nums, temp, result, used);
                used[i] = false;
                temp.pop_back();
            }            
        }        
    }    
};
$\endgroup$
1
$\begingroup$

(1) You are sorting the vector so duplicate values will be consecutively present in the vector.

(2) Now we come to the logic behind that condition:

  • As the vector can contain the duplicates we should make sure not to repeat the same sequence by starting with the same element again(duplicate)
    • example :
      • 1,1,2 (starting with first one) and 1,1,2 (starting with second one) => both are same (we should make sure this doesn't happen)

Example: In [1, 1, 2]

  • If the first element in the sequence is chosen as 1, then we should make sure we are not going to create another sequence starting with another 1 (duplicate of the element).

  • So for that, we need to skip the loop for all the consecutive duplicate elements.

  • In your case, after creating a sequence staring with first 1, when we enter the loop for the second time we check whether the current element is a duplicate nums[i] == nums[i - 1] (this is sufficient as you have already sorted the vector) and whether the current element is the first element of the sequence !used[i - 1].

    • In your case, due to this condition, the second one cannot be the first element of the sequence.
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.