09. Subsets II (Duplicates Handling)

Difficulty:HardPattern:Backtracking Duplicate SkipTime:O(2^n)Space:O(n)

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

How It Works & Algorithmic Design

Solves using Sorted Input Backtracking with Duplicate Pruning:

Sort: Sort nums so identical values are adjacent.
Backtracking DFS dfs(start, path):
- Push copy of path to results.
- Loop $i$ from start to nums.length:
  - Duplicate Pruning: If $i > \text{start}$ and nums[i] === nums[i - 1], continue.
  - Add nums[i] to path.
  - Recurse dfs(i + 1, path).
  - Backtrack: remove nums[i].

Why This Approach Works Best

Pruning duplicate branches at the loop level prevents duplicate subsets without needing post-processing hash sets.

Example Walkthrough

Input: nums = [1, 2, 2]

Array with duplicate values.

Pruned Branching: Skip second '2' at loop level $i > start$.

Avoids identical power set outputs.

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

Unique subsets.

Answer: Subsets II implementation

function subsetsWithDup(nums) {
  nums.sort((a, b) => a - b);
  const res = [];
  function backtrack(start, path) {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      if (i > start && nums[i] === nums[i - 1]) continue;
      path.push(nums[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }
  backtrack(0, []);
  return res;
}

💡 Sort array to bring duplicate elements together and skip duplicate sibling branch calls.

Key Takeaways

Sort input array first to group identical elements.
Skip condition i > start && nums[i] === nums[i-1] prevents duplicate subtree calls.
Generates all $2^n$ subsets without hash set overhead.