Power Set with Duplicates
Application of Backtracking

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
Problem Statement:
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
The solution set must not contain duplicate subsets.
Example:
Input: [1,2,2]
Output:
[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
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.
We use the Lexicographic Order solution for Computing Power Set for Unique Elements, and just handle duplicate subsets so that we do not have any subset more than once in the power set.
Here is how we get duplicate subsets:
Suppose, nums[] = {2, 2}. We could get the subset [2, 2] twice in following two ways:
[nums[0], nums[1]] and [nums[1], nums[0]]
We could also get [2] twice instead of just once in following two ways:
[nums[0]] , [nums[1]]
So we would be able to avoid printing same subset more than once by following the below rule:
 if nums[i + 1] == nums[i] then do not include nums[i + 1] as a candidate for the first position in the power set for nums[i...(n  1)], where n = total number of elements in nums[].
The code below implements the above logic to handle duplicate configurations (subsets).
Java Code:
Login to Access Content
Python Code:
Login to Access Content
Approach #2: Compute all subsets (without handling the duplicate subsets explicitly) and store them in a SET so that duplicate subsets are eliminated:
We would modify the above implementation to accommodate for duplicates. We do the below couple modifications/additions to achieve this:

We sort the
partialSolution
lists before putting them incompleteSolution
data structure. That way all the partialSolutions with same elements would look same. A partialSolution with 4, 1, 4 will always look like [1, 4, 4], and not [4, 4, 1] or [4, 1, 4]. 
We take
HashSet
to represent the completeSolution sinceSet
eliminates duplicates.
Java Code:
Login to Access Content
Python Code:
Login to Access Content
Don't forget to take an indepth look at the other backtracking problems in the below link, because that is what would make you comfortable with using the backtracking template and master the art of Backtracking and be an overachiever:
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.