Power Set with Duplicates
Application of Backtracking

Customer Support: admin@thealgorists.com

Feedback Form:
https://www.thealgorists.com/Feedback.

Manage Subscriptions:
https://www.thealgorists.com/CustomerPortal
(Make sure you are logged into https://www.thealgorists.com.)
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:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Python Code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
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:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Python Code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
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:
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