Subsets II

Subsets II

What is this problem about?

"Subsets II" is the natural follow-up to the Subsets problem. The key difference is that the input array can now contain duplicate elements. Your task is still to return all possible subsets, but the result must not contain any duplicate subsets. For example, if the input is [1, 2, 2], the subsets [1, 2] and [1, 2] (using the different 2s) should only appear once in your final list.

Why is this asked in interviews?

Companies like Meta, Amazon, and TikTok ask this to see if you can handle "Duplicate Removal" in a recursive context. It's one thing to generate all combinations; it's another to do so efficiently without generating and then filtering out duplicates. It tests if a candidate knows the trick of sorting the input and using a simple condition to skip duplicate elements during recursion.

Algorithmic pattern used

The pattern used is Backtracking with Pruning.

1. Sort the input array. This is essential because it brings duplicate elements together.
2. During the recursive step, if you are at an index i and arr[i] == arr[i-1], and you have already skipped arr[i-1], you should also skip arr[i]. This simple "skip" condition ensures that for any group of duplicate numbers, you only generate subsets that include them in a consistent way (e.g., always use the first occurrence before the second), thus preventing duplicate subsets from being formed.

Example explanation (use your own example)

Array: [2, 1, 2].

1. Sort the array: [1, 2, 2].
2. Start recursion:
   • Include 1: [1]
     • Include first 2: [1, 2]
       • Include second 2: [1, 2, 2]
       • Skip second 2: [1, 2]
     • Skip first 2: [1] -> (Now we see the next element is also 2. We skip it to avoid duplicates).
   • Skip 1: []
     • Include first 2: [2]
       • Include second 2: [2, 2]
       • Skip second 2: [2]
     • Skip first 2: [] Final unique subsets: [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]].

Common mistakes candidates make

The most frequent mistake is forgetting to sort the array first. Without sorting, the "skip duplicate" logic won't work because duplicates won't be adjacent. Another mistake is using a Hash Set to store subsets to remove duplicates at the end. While this works, it is less efficient than pruning the recursion tree and is often frowned upon in high-level interviews as it shows a lack of control over the generation process.

Interview preparation tip

When preparing for the Subsets II interview question, focus on the "Skip Condition": if (i > start && nums[i] == nums[i-1]) continue;. Practice explaining why this works—it's about ensuring that we don't start a new branch with a number we've already tried at the same level of the recursion tree.