• 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.



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 rock-solid 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 in completeSolution 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 since Set 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 in-depth 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 over-achiever:



The above content is written by:

Abhishek Dey

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

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave