Permutations with Duplicates
A Backtracking Problem

Customer Support: admin@thealgorists.com

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.
 If you are a student, email to admin@thealgorists.com to get special student discount.
Problem Statement:
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Example 1:
Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]
Example 2:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Solution:
 NOTE: I highly recommend going through the Backtracking chapters in the order they are given in the Index page to get the most out of it and be able to build a rocksolid understanding.
The solution for this problem would be very similar to that of Computing Permutations, except that here we would have to handle duplicate elements properly to make sure we do not print any permutation more than once.
Now let's see when and how you could get same permutation more than once, if we do not handle the duplicates properly:
Let's say we have nums[] = {1, 3, 3, 3} as input.

We could get the permutation [1, 3 , 3, 3] more than once in the following ways:
[nums[0], nums[1], nums[2], nums[3]] ,
[nums[0], nums[1], nums[3], nums[2]] ,
[nums[0], nums[2], nums[1], nums[3]] ,
[nums[0], nums[2], nums[3], nums[1]] ,
[nums[0], nums[3], nums[1], nums[2]] ,
[nums[0], nums[3], nums[2], nums[1]] .
If you notice closely, we could have avoided all the duplicate permutations if for each position in partial solution we would have included any duplicate element only once. Put in a different way, for each position in partial solution only one instance of the duplicate elements is allowed. What I meant is: in the above example at index 1 for the permutations we should have had either nums[1] or nums[2] or nums[3] as candidates but not all of them. To achieve this we could implement the below strategy:
 Whenever we are including a duplicate element as a candidate for a certain position in partial solution, we could just include the first unused instance of the duplicate element in SORTED input.
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
The above content is written by:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn