Subsets II Medium 0 attempts
LeetCode ↗

Subsets II

Medium BacktrackingRecursion LeetCode

You're given an integer array nums that might contain repeated values. Generate every possible subset (the power set), making sure no two subsets in the result are identical. The subsets can be returned in any order.

Input Format
Implement subsetsWithDup(nums). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. The order of the outer result array does not matter. Result ordering is ignored, including element order within each combination or subset.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
nums = [0]
Output
[[],[0]]
Constraints
  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
Test Cases (2)
Case 1
Args: [[1,2,2]] Expected: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Case 2
Args: [[0]] Expected: [[],[0]]
Topics
BacktrackingRecursion

Sort the array first so duplicates are adjacent. During backtracking, skip an element if it's the same as the previous one at the same recursion depth — this prevents duplicate subsets from being generated.

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

  function backtrack(start, current) {
    result.push([...current]);
    for (let i = start; i < nums.length; i++) {
      if (i > start && nums[i] === nums[i - 1]) continue;
      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop();
    }
  }

  backtrack(0, []);
  return result;
}

Time: O(n * 2^n) — up to 2^n subsets, each copied in O(n). Space: O(n) for the recursion stack.

Saved in this browser only. Private to you.

JavaScript