Subsets II
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]]
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;}