Subsets II

The problem. Given an integer array nums that may contain duplicates, return all possible subsets. The answer must not contain duplicate subsets.

Example

nums = [1, 2, 2]  ->  [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
nums = [0]        ->  [[], [0]]

The idea: sort, then skip equal neighbours at the same level

Use the loop-from-start template: the node for a subset tries adding each number at or after start, and every node is itself an answer. Duplicates appear when two equal values are tried at the same level: taking the first 2 and taking the second 2 lead to identical subtrees. Sort first so equal values sit together, then at each level skip a value equal to the one just tried: if (i > start && nums[i] === nums[i − 1]) continue. Taking a 2 and then another 2 deeper down is still allowed — that's i == start.

1. All subsets, then remove repeats

1function subsetsWithDup(nums) {2  const sorted = [...nums].sort((a, b) => a - b);   // so equal subsets look the same3  const seen = new Set();4  const result = [];5  for (let mask = 0; mask < 1 << sorted.length; mask++) {6    const s = sorted.filter((_, j) => mask & (1 << j));7    const key = s.join(",");8    if (!seen.has(key)) {9      seen.add(key);10      result.push(s);11    }12  }13  return result;14}

Time O(n · 2ⁿ), space O(n · 2ⁿ) for the set. It builds every repeat only to throw it away.

2. Backtracking that never builds a repeat

1function subsetsWithDup(nums) {2  const a = [...nums].sort((x, y) => x - y);   // equal values next to each other3  const result = [];4  const path = [];5  const build = (start) => {6    result.push([...path]);                    // every node is a subset7    for (let i = start; i < a.length; i++) {8      if (i > start && a[i] === a[i - 1]) continue;   // same value at the same level: a repeat9      path.push(a[i]);10      build(i + 1);11      path.pop();12    }13  };14  build(0);15  return result;16}

Time O(n · 2ⁿ) in the worst case (all distinct), space O(n) besides the output. With many duplicates the tree is much smaller than 2ⁿ, because the repeats are never built.

Comparing the approaches

Edge cases to test

Variations