Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumbacktracking

Subsets II

Problem (restated)

Return all unique subsets of an integer array that may contain duplicates.

Intuition

Same power-set DFS as Subsets, but sort first and skip equal siblings at the same depth.

Approaches

Sort + skip duplicates

Unverified

Time O(n * 2^n)Space O(n)

Idea. Sort; at start i, if nums[i]==nums[i-1] and i>start, continue (same choice already explored).

Walkthrough. [1,2,2] → [], [1], [1,2], [1,2,2], [2], [2,2] - no duplicate [1,2].

Trade-offs. Skipping only at the same level preserves multi-copy subsets via successive picks.

Solution

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

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

Template connection

Backtracking with duplicate pruning (like Combination Sum II).

Reflection

Sort first. At the same depth, skip nums[i] when it equals nums[i - 1]. That is the duplicate subset.
Further down, taking the same value again is allowed. [1, 2, 2] really does contain two 2s.
All values equal. An empty array answers [[]]. Skip the sort and the skip rule does nothing.