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(); } } } };
Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.
Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.