Subsets II

MediumBacktrackingArrayBacktrackingBit Manipulation

Problem

Given an array of integers that may contain duplicates, return every possible subset, with duplicate subsets removed from the output. As with plain subset generation, order between and within subsets does not matter, and the empty subset counts as one of the outputs.

Example. For [1, 2, 2], the subsets are [], [1], [2], [1,2], [2,2], and [1,2,2]. The naive include/exclude tree would otherwise also produce [1,2] and [2] a second time by way of the second 2.

Key idea

This is the same include/exclude decision tree used for plain Subsets, with one added complication: duplicate values let the tree reach the same subset through two different paths, for example by treating "the first 2" and "the second 2" as interchangeable. Sorting the array up front turns this into a local rule instead of requiring a hash set of already-seen subsets.

After sorting, walk the array by index as in Subsets, recording the partial subset at each step and recursing over both "include" and "skip." The fix lives in the skip branch: once you decide not to include the current element, skip over every subsequent element equal to it before moving on, so a run of equal values can only ever be "started" by including its first occurrence. This stops the tree from re-deriving the same subset from a later duplicate standing in for an earlier one, since inclusion within a run of duplicates always proceeds left to right.

Solution

function subsetsWithDup(nums: number[]): number[][] {
  const sorted = [...nums].sort((a, b) => a - b);
  const result: number[][] = [];
  const partial: number[] = [];

  function backtrack(index: number): void {
    if (index === sorted.length) {
      result.push([...partial]);
      return;
    }

    // Include the current element.
    partial.push(sorted[index]);
    backtrack(index + 1);
    partial.pop();

    // Skip the current element, and skip the rest of this run of duplicates
    // so a repeated value can only ever be "started" by its first occurrence.
    let next = index + 1;
    while (next < sorted.length && sorted[next] === sorted[index]) {
      next++;
    }
    backtrack(next);
  }

  backtrack(0);
  return result;
}

Complexity

  • Time: O(n · 2ⁿ). The same asymptotic bound as Subsets, since pruning removes duplicate branches without changing the worst-case shape.
  • Space: O(n). Recursion depth and the partial subset, excluding the output.

Watch out for

  • Sort first; the duplicate-skip rule only works once equal values are adjacent.
  • The skip-ahead rule belongs to the "not including" branch only; including a duplicate at its own turn in the recursion is still correct and necessary.

Pattern

This is Subsets combined with the same-level duplicate-skipping trick used in Combination Sum II, the standard way backtracking handles distinct output over duplicate input.

Related questions