How do you solve Subsets II?

The algorithm sorts nums, then uses a recursive backtracking function that explores subsets by including or excluding elements. Before recursing on the exclusion path, it advances the index to skip duplicates. This ensures that subsets differing only by the position of duplicate elements are not generated multiple times. The result is a complete, duplicate-free set of subsets generated in O(2^n) time, which is optimal for subset enumeration.

Subsets II

Q: What is the time complexity of Subsets II?

O(2^n). The algorithm explores all unique subsets. In the worst case with no duplicates, there are 2^n subsets. Sorting takes O(n log n), which is dominated by the subset generation.

Q: What pattern does Subsets II use?

The Pattern: Backtracking (State Restoration with Duplicate Skipping) The Heuristic: When generating subsets with duplicates, sort the input and skip over duplicate elements at the same recursion depth to prune redundant branches, ensuring each unique subset is generated exactly once without extra post-processing.

Medium Backtracking

Problem

Given an integer array nums that may contain duplicates, return all possible subsets (the power set) without duplicate subsets. The solution set must not contain duplicate subsets. Return the solution in any order.

1 ≤ nums.length ≤ 10
−10 ≤ nums[i] ≤ 10

Example

Input: nums = [1,2,2]

Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

The brute-force approach generates all subsets without considering duplicates, resulting in duplicate subsets like [1,2] appearing multiple times. The algorithm first sorts nums to group duplicates together. It then uses backtracking to explore subsets, carefully skipping over duplicate elements at the same recursion depth to avoid generating duplicate subsets. For example, after including the first '2', the algorithm skips the second '2' at the same level to prevent duplicate subsets. This pruning ensures each unique subset is generated exactly once.

Approach

Straightforward Solution

A naive backtracking approach generates all subsets by including or excluding each element, resulting in 2^n subsets. However, with duplicates, this approach produces duplicate subsets, requiring post-processing or extra checks, which is inefficient.

Core Observation

The fundamental challenge is to generate all subsets while avoiding duplicates caused by repeated elements. Sorting the input groups duplicates, enabling the algorithm to detect and skip over repeated elements during recursion to prevent duplicate subsets.

Path to Optimal

Preview

Sorting the array is the key insight, as it places duplicates consecutively. During backtracking, when deciding whether to include or exclude an element, the algorithm skips over duplicates at the same recursion depth by advancing the index past repeated values…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

The algorithm sorts nums, then uses a recursive backtracking function that explores subsets by including or excluding elements. Before recursing on the exclusion path, it advances the index to skip duplicates…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(2^n)

The algorithm explores all unique subsets. In the worst case with no duplicates, there are 2^n subsets. Sorting takes O(n log n), which is dominated by the subset generation.

Space

O(n)

The recursion stack and the temporary subset list use O(n) space. The output list size is O(2^n), but this is not counted as auxiliary space.

Pattern Spotlight

Backtracking (State Restoration with Duplicate Skipping)

When generating subsets with duplicates, sort the input and skip over duplicate elements at the same recursion depth to prune redundant branches, ensuring each unique subset is generated exactly once without extra post-processing.

Solution

Python

1class Solution:
  def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
      res = []
      nums.sort()
      
      def backtrack(i, subset):
          if i == len(nums):
              res.append(subset.copy())
              return
          
          subset.append(nums[i])
          backtrack(i + 1, subset)
          subset.pop()
14
          while i + 1 < len(nums) and nums[i] == nums[i + 1]:
              i += 1
          backtrack(i + 1, subset)
18
      backtrack(0, [])
      return res

Step-by-Step Solution

Sort Input to Group Duplicates for Pruning

4	`nums.sort()`

Objective

To arrange the input array so that duplicate elements are adjacent, enabling efficient duplicate skipping during backtracking.

Key Insight

Sorting is a crucial preprocessing step that clusters duplicates together. This ordering allows the backtracking algorithm to detect consecutive duplicates easily and skip them at the same recursion depth, preventing redundant subset generation. Without sorting, duplicates would be scattered, making pruning impossible or inefficient.

Interview Quick-Check

Core Logic

Sorting groups duplicates, which is essential for the pruning logic that skips repeated elements during recursion.

Common Pitfalls & Bugs

Failing to sort leads to duplicate subsets because the algorithm cannot detect duplicates efficiently.

Explore Subsets via Backtracking with Duplicate Skipping

To recursively build subsets by deciding whether to include each element, while skipping duplicates to avoid redundant subsets.

Initiate Backtracking and Return All Unique Subsets

To start the recursive exploration from the first element and return the collected unique subsets.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 8 Critical

res.append(subset.copy())

Add a copy of the current subset to the results list.

Copying the subset is critical to preserve the current state, as the subset list is mutated during backtracking; without copying, all results would reference the same list.

Line 13 Critical

subset.pop()

Remove the current element to backtrack and restore state.

This 'un-choose' step is critical to restore the subset state before exploring subsets that exclude the current element, enabling correct exploration of all branches.

Line 4 Critical

nums.sort()

Sort the input array to group duplicate elements together.

Sorting is essential to enable the pruning logic that skips duplicates during recursion, preventing duplicate subsets.

Full line-by-line criticality + rationale for all 14 lines available on Pro.

Test Your Understanding

Why does skipping duplicates at the same recursion depth prevent generating duplicate subsets?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Subsets II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Subsets II drill

or drill a free problem

1	`class Solution:`
2	`def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:`
3	`res = []`
4	`nums.sort()`
5
6	`def backtrack(i, subset):`
7	`if i == len(nums):`
8	`res.append(subset.copy())`
9	`return`
10
11	`subset.append(nums[i])`
12	`backtrack(i + 1, subset)`
13	`subset.pop()`
14
15	`while i + 1 < len(nums) and nums[i] == nums[i + 1]:`
16	`i += 1`
17	`backtrack(i + 1, subset)`
18
19	`backtrack(0, [])`
20	`return res`