Subsets II

Examples

Input: nums = [1, 2, 2]
Output: [[], [1], [2], [1,2], [2,2], [1,2,2]]

Without de-duplication you'd also get a second [1,2] and a second [2] (from picking either of the two 2s) - those repeats are left out.

Input: nums = [4, 4, 4, 1]
Output: [[], [1], [4], [4,1], [4,4], [4,4,1], [4,4,4], [4,4,4,1]]

The three 4s are indistinguishable, so a subset is defined only by how many 4s it contains (0-3), not which ones.

Constraints

• 1 <= nums.length <= 10

• -10 <= nums[i] <= 10

Approach

This is the same include/exclude exploration as the plain subsets problem, except that duplicate values in the input can make the search visit the exact same subset from two different paths - for example, choosing "the first 2" versus "the second 2" produces an identical-looking subset either way.

A brute-force fix is to run the ordinary subset search exactly as before, letting it produce duplicate subsets, and then filter the results afterward - for instance by turning each subset into a sorted, stringified key and only keeping the first subset seen for each key.

A more direct fix avoids ever generating the duplicate in the first place: sort the input so identical values become neighbors, and while deciding what to include next at a given step, skip over a value if it's identical to the value you just decided not to include at that same step. That one rule prevents the search from ever re-exploring a branch it's effectively already covered.

Solutions

Brute Force — Generate Then De-duplicate

Run the same include/exclude backtracking as ordinary subsets, without worrying about duplicate values at all. This produces every subset, including repeats of the same subset reached through different combinations of equal values. Afterward, collapse duplicates by keying each subset on its sorted, comma-joined values and keeping only one copy per key.

function subsetsWithDup(nums) {
  const all = [];
  const current = [];

  function backtrack(index) {
    if (index === nums.length) {
      all.push([...current]);
      return;
    }
    current.push(nums[index]);
    backtrack(index + 1);
    current.pop();
    backtrack(index + 1);
  }

  backtrack(0);

  const seen = new Set();
  const result = [];
  for (const subset of all) {
    const key = [...subset].sort((a, b) => a - b).join(",");
    if (!seen.has(key)) {
      seen.add(key);
      result.push(subset);
    }
  }

  return result;
}

Time: O(2^n * n) to generate every subset, plus O(2^n * n) to key and de-duplicate them · Space: O(2^n * n) for the raw subsets and the de-duplication set

Optimal — Sort and Skip Duplicate Branches

Sort the input first, then build subsets by deciding, at each index, whether to include it or move past it - but skip an "include" choice when this value is identical to the previous element in the sorted array at this same step, since that would explore a branch already fully covered by the first occurrence.

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

  function backtrack(start) {
    result.push([...current]);

    for (let i = start; i < sorted.length; i++) {
      if (i > start && sorted[i] === sorted[i - 1]) continue; // skip duplicate at this level

      current.push(sorted[i]);
      backtrack(i + 1);
      current.pop();
    }
  }

  backtrack(0);
  return result;
}

Time: O(2^n * n) · Space: O(n) auxiliary (recursion + current array), plus O(2^n * n) output