Subsets II

Medium

Problem

The array may contain duplicates. Return every possible subset, with no duplicate subsets in the result.

Example 1

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

Test cases

Case 1

Input:    [1,2,2]
Expected (any order): [[],[1],[1,2],[1,2,2],[2],[2,2]]

Case 2

Input:    [0]
Expected (any order): [[],[0]]

Case 3

Input:    [2,2]
Expected (any order): [[],[2],[2,2]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Sort + skip equal siblings

Time O(n · 2^n)Space O(n)

Sort so duplicates are adjacent. At one recursion level, use a repeated value only for its first occurrence (i > start && nums[i] === nums[i − 1] → skip).

function subsetsWithDup(nums) {
nums.sort((a, b) => a - b);
const res = [], path = [];
const bt = (start) => {
res.push([...path]);
for (let i = start; i < nums.length; i++) {
if (i > start && nums[i] === nums[i - 1]) continue;
path.push(nums[i]);
bt(i + 1);
path.pop();
}
};
bt(0);
return res;
}