90. Subsets II

At a Glance

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

Problem (one-liner)

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

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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