90. Subsets II

Given an integer array nums that may contain duplicates, return all possible subsets (the power set) without duplicate subsets, in any order.

Sort, then backtrack as in Subsets. At each depth, only the first of several equal values may be chosen; picking a later copy would build the same subsets again.

1function subsetsWithDup(nums: number[]): number[][] {
2  nums.sort((a, b) => a - b);
3  const res: number[][] = [], path: number[] = [];
4  function dfs(start: number) {
5    res.push([...path]);
6    for (let i = start; i < nums.length; i++) {
7      if (i > start && nums[i] === nums[i - 1]) continue;
8      path.push(nums[i]);
9      dfs(i + 1);
10      path.pop();
11    }
12  }
13  dfs(0);
14  return res;
15}

path = []

nums

start

subsets

[]

Record [].

1 / 0

Space: play/pause · ←/→: step