Subsets II Medium 0 attempts
LeetCode ↗

Subsets II

Medium BacktrackingRecursion LeetCode

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

Examples

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

Input: nums = [0]
Output: [[], [0]]

Constraints

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
Sample Input
nums = [1,2,2]
Sample Output
[[],[1],[1,2],[1,2,2],[2],[2,2]]
Constraints
  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
Test Cases
Case 1
Args: [[1,2,2]] Expected: [[],[1],[1,2],[1,2,2],[2],[2,2]]
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.

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