🙏

জয়  শ্রী  রাম

🕉

---

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:

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 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:

Login to Access Content

Python Code:

Login to Access Content




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:

• All Backtracking Problems in one place

Instructor: