90. Subsets II

Quick Identifier

Topic: backtracking
Pattern: DFS / Backtracking
Difficulty: Medium
Companies: Amazon, Google, Microsoft, Meta, Apple
Frequency: High
LeetCode: 90

Quick Sights

Time Complexity: O(2^n) from the optimal approach.
Space Complexity: O(recursion depth) excluding the final output unless stated.
Core Mechanism: Given nums that may contain duplicates, return all unique subsets. The list must not contain duplicate subsets.

Concept Explanation

Given nums that may contain duplicates, return all unique subsets. The list must not contain duplicate subsets.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

Same as subsets but duplicates in input
Sort first, then at each tree level skip nums[index] == nums[index-1] when index > start

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Set hash of tuple — works, heavier memory.
Optimal — sort + skip rule in DFS — O(2^n) with dedupe.

Optimal Solution

Go

import "sort"

func subsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)
	result := [][]int{}
	path := make([]int, 0, len(nums))

	var dfs func(start int)
	dfs = func(start int) {
		copied := make([]int, len(path))
		copy(copied, path)
		result = append(result, copied)
		for index := start; index < len(nums); index++ {
			if index > start && nums[index] == nums[index-1] {
				continue
			}
			path = append(path, nums[index])
			dfs(index + 1)
			path = path[:len(path)-1]
		}
	}
	dfs(0)
	return result
}

JavaScript

function subsetsWithDup(nums) {
  nums.sort((left, right) => left - right);
  const result = [];
  const path = [];

  function dfs(startIndex) {
    result.push([...path]);
    for (let index = startIndex; index < nums.length; index += 1) {
      if (index > startIndex && nums[index] === nums[index - 1]) {
        continue;
      }
      path.push(nums[index]);
      dfs(index + 1);
      path.pop();
    }
  }

  dfs(0);
  return result;
}

Walkthrough

[1,2,2]. Subsets: [],[1],[2],[1,2],[2,2],[1,2,2]. Skipping second 2 at wrong level would drop valid [2,2], but at same start the rule keeps unique tree branches.

Invariant: Duplicates are only expanded the first time at a given recursion depth from start.

Edge Cases

All same value
Length 1

Pitfalls

Skipping when index == start — would remove valid repeated values in the path (use index > start for same-level dedupe)

Variants

Count unique subsets only — meet-in-the-middle with care

Mind-Map Tags

#backtracking #subsets #dedupe #sort #dfs