Subsets II

You are given an array nums of integers, which may contain duplicates. Return all possible subsets.

The solution must not contain duplicate subsets. You may return the solution in any order.

Examples

• 1 ≤ nums.length ≤ 11
• -20 ≤ nums[i] ≤ 20

Prerequisites

Before attempting this problem, you should be comfortable with:

• Backtracking - The core technique for exploring all possible subsets through recursive inclusion/exclusion decisions
• Sorting - Required to group duplicate elements together so they can be properly skipped
• Recursion - Understanding how to build solutions incrementally and backtrack when needed

1. Brute Force

Intuition

This brute-force method generates every possible subset by making a binary choice at each index. Since duplicates exist, many generated subsets may look identical. To avoid returning duplicates, we sort the array first, and store each subset as a tuple inside a set, which automatically removes duplicates.

Time: O(n * 2ⁿ), Space: O(2ⁿ)

2. Backtracking I (Skip While Loop)

Intuition

Instead of blindly generating all subsets, we avoid picking the same value in the same decision level more than once. When excluding a number, if the next number is the same (nums[i] == nums[i+1]), skipping it now and skipping it later produce the same subset. So after exploring the "exclude" branch, we use a while loop to skip over all duplicate values.

3. Backtracking II (Loop & Continue)

Intuition

Instead of making "pick / not pick" decisions, this approach builds subsets by choosing each possible next element from a loop—but only once per unique value at each recursion level.

We sort the array. At each recursion level, we loop j from the current index to the end. If nums[j] == nums[j-1] and j > i, we continue to skip it. Every time we enter the function, we push the current subset to the results.

4. Iteration

Intuition

Normally, for each new number, we add it to every existing subset. But duplicates cause repeated subsets. If the current number is a duplicate, we only combine it with subsets created in the last round to prevent duplicate generation.

Common Pitfalls

Forgetting to Sort the Array First

Sorting is essential because it groups duplicate elements together, enabling the skip logic to work correctly. Without sorting, duplicates scattered throughout the array cannot be detected and skipped, resulting in duplicate subsets.

Incorrect Duplicate Skipping Condition

The condition j > i && nums[j] == nums[j-1] must use j > i, not j > 0 or j >= i. Using j > 0 would skip the first occurrence of a duplicate at each recursion level, missing valid subsets. The check ensures we only skip duplicates after the first one at the current decision level.

Modifying the Subset Reference Incorrectly

When adding subsets to the result, you must copy the current subset (e.g., subset[:] in Python or new ArrayList<>(subset) in Java). Adding the reference directly means all entries in the result will point to the same list, which gets modified during backtracking.