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

Tested only

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

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?