AlgoMaster Logo

Subsets II

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We need to generate every possible subset of the input array, like the classic Subsets problem (LeetCode #78). The difference here is that the input can contain duplicates, and the result must not include duplicate subsets.

For example, given [1, 2, 2], the subset [1, 2] should appear only once, even though there are two 2s we could pick from. The problem is to generate subsets systematically while skipping choices that would produce a set already built.

Sorting the array first groups duplicates together, which gives a clean way to detect and skip them during generation.

Key Constraints:

  • 1 <= nums.length <= 10 → With n at most 10, the total number of subsets is at most 2^10 = 1024. An exponential approach is acceptable.
  • -10 <= nums[i] <= 10 → The value range is small relative to the array length, so duplicates are common. A deduplication strategy is needed.

Approach 1: Brute Force (Generate All, Then Deduplicate)

Intuition

Ignore the duplicates entirely, generate all 2^n subsets like the classic Subsets problem, then remove duplicates at the end. Because the array is sorted before generation, two subsets that contain the same values also contain them in the same order, so storing each subset in a set deduplicates them by value.

This adapts a working Subsets solution with minimal changes. It is wasteful, since it generates subsets only to discard them.

Algorithm

  1. Sort the input array.
  2. Use backtracking to generate all 2^n subsets (include or exclude each element).
  3. For each generated subset, convert it to a tuple (or sorted string) and add it to a set to track uniqueness.
  4. Collect all unique subsets into the result.

Example Walkthrough

Input:

0
1
1
2
2
2
nums

After sorting, nums = [1, 2, 2]. The include/exclude recursion generates all 2^3 = 8 subsets. Listing them in generation order: [1,2,2], [1,2], [1,2], [1], [2,2], [2], [2], []. Two of them repeat: [1,2] appears twice (one 2 picked from each duplicate position) and [2] appears twice. The set keeps one copy of each, leaving 6 unique subsets:

1
1
2
1
2
2
2
2
2
result

Code

Generating duplicates only to discard them is avoidable. The next approach prunes duplicate branches during generation, so no subset is built twice.

Approach 2: Backtracking with Pruning (Optimal)

Intuition

Instead of generating everything and filtering, prevent duplicates from being generated at all. Sort the array so identical values are adjacent, then apply one rule during backtracking: at each decision level, do not pick the same value more than once.

When building subsets by choosing elements from index start onward, we iterate through candidates. If a value matches the previous candidate at the same level (nums[i] == nums[i-1] and i > start), we skip it. The previous candidate already explored every subset that starts with that value from this position, so picking the same value again would regenerate the identical set of subsets.

Algorithm

  1. Sort the input array so duplicates are adjacent.
  2. Start backtracking with an empty current subset and start = 0.
  3. At each recursive call, add the current subset to the result (every state is a valid subset).
  4. Iterate from start to n - 1, picking each element as the next addition.
  5. If i > start and nums[i] == nums[i - 1], skip this element (it would create a duplicate branch).
  6. Add nums[i] to the current subset, recurse with start = i + 1, then remove nums[i] (backtrack).

Example Walkthrough

1Start: backtrack(start=0, current=[]), add [] to result
0
1
start
1
2
2
2
1/9
1Add empty subset []
[]
1/9

Code

The backtracking approach uses optimal time and linear extra space. The same result can be built iteratively, without recursion.

Approach 3: Iterative Construction

Intuition

The iterative approach builds subsets one element at a time. Start with the empty set [[]]. For each new element, take every existing subset and create a new version with the element appended, then add all these new subsets to the result.

Handling duplicates changes one detail. When the current element equals the previous one, we do not extend every existing subset. We extend only the subsets that were added in the previous iteration. Extending the older subsets would recreate the ones already produced when the first occurrence of this value was processed.

Algorithm

  1. Sort the input array.
  2. Initialize result = [[]], containing only the empty subset.
  3. Track prevNewCount, which stores how many new subsets were added in the last step.
  4. For each element nums[i]:
    • If nums[i] == nums[i-1] (duplicate), only extend the last prevNewCount subsets from the result.
    • Otherwise, extend all subsets in the result.
    • Append each new subset to the result and update prevNewCount.

Example Walkthrough

nums (sorted)
1Start: result = [[]], process each element left to right
0
1
1
2
2
2
result
1Initial: result contains only the empty subset
0
1/5

Code