Subsets II

Given an integer array nums that may contain duplicates, return every distinct subset of it (its power set without repeats). Two subsets count as the same if they contain the same values with the same multiplicities, regardless of which positions they came from.

The empty subset is always included. You may return the subsets in any order, and the values inside each subset in any order too.

Without duplicates, subsets come from a simple backtracking tree: at each level you choose the next index to add, always moving forward so each combination is built once.

Duplicates break that because two equal values at different positions lead to identical branches. The fix is to sort first, so equal values sit next to each other, then apply one rule: at a given level of the tree, only the first copy of a value may start a branch. If nums[i] == nums[i-1] and i isn't the first option at this level, skip it, because the branch starting at i-1 already produced everything the branch at i would.

You can still take several copies of a value; they just have to be taken by going deeper (copy 1, then copy 2 at the next level), never as sibling choices.

def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    nums = sorted(nums)
    result = []
    path = []

    def backtrack(start: int) -> None:
        result.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue  # same value already tried at this level
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

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

  const backtrack = (start) => {
    result.push([...path]);
    for (let i = start; i < sorted.length; i++) {
      if (i > start && sorted[i] === sorted[i - 1]) continue; // same value already tried at this level
      path.push(sorted[i]);
      backtrack(i + 1);
      path.pop();
    }
  };

  backtrack(0);
  return result;
}

Start from the version without duplicates and say what goes wrong: equal values at different positions generate the same branch twice. Then introduce sorting and the sibling-skip rule as the fix. Interviewers want to hear why i > start and not i > 0; trace [5, 5] to show the difference.

The same skip rule shows up in Combination Sum II and Permutations II, so pointing that out signals you recognize the family.