LeetCode 90: Subsets II

Problem Restatement

We are given an integer array nums.

Unlike LeetCode 78, this array may contain duplicate values.

We need to return all possible subsets, also called the power set.

The answer must not contain duplicate subsets.

The subsets may be returned in any order.

The official statement says that nums may contain duplicates, the solution set must not contain duplicate subsets, and the constraints are 1 <= nums.length <= 10 and -10 <= nums[i] <= 10.

Input and Output

Function shape:

class Solution:
    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        ...

Examples

Example 1:

nums = [1, 2, 2]

All unique subsets are:

[
    [],
    [1],
    [1, 2],
    [1, 2, 2],
    [2],
    [2, 2],
]

We include [1, 2] only once, even though there are two 2 values in the input.

Example 2:

nums = [0]

The possible subsets are:

[
    [],
    [0],
]

Example 3:

nums = [1, 1]

The unique subsets are:

[
    [],
    [1],
    [1, 1],
]

Without duplicate handling, [1] would be generated twice.

First Thought: Generate Everything, Then Deduplicate

A simple method is to generate all subsets using normal backtracking, then store each subset in a set.

Because lists cannot be stored directly in a set, we would convert each subset into a tuple.

seen = set()
seen.add(tuple(path))

This works, but it is not ideal.

It generates duplicate work first, then removes duplicates afterward.

We can avoid duplicate subsets during generation.

Key Insight

Sort the array first.

nums.sort()

Sorting groups equal values together.

For example:

[2, 1, 2]

becomes:

[1, 2, 2]

Now duplicates are adjacent.

During backtracking, at the same recursion level, if we already tried one value, we should skip later copies of the same value.

The key rule is:

if i > start and nums[i] == nums[i - 1]:
    continue

This means:

If this is not the first candidate at the current level, and it equals the previous candidate, skip it.

Why the Skip Rule Works

Use:

nums = [1, 2, 2]

At the top level, possible first choices are:

1
2
2

The two 2 choices would both create the same family of subsets:

[2]
[2, 2]

So at the same recursion level, we only allow the first 2.

However, after choosing one 2, we are allowed to choose the next 2 deeper in the recursion.

That is how we still generate:

[2, 2]

The distinction is important:

Algorithm

1. Sort nums.
2. Create an empty answer list ans.
3. Create an empty current subset path.
4. Define backtrack(start).
5. At the start of every call, copy path into ans.
6. Loop i from start to the end of nums.
7. If nums[i] duplicates the previous value at the same level, skip it.
8. Otherwise, choose nums[i], recurse with i + 1, then undo the choice.
9. Return ans.

Walkthrough

Use:

nums = [1, 2, 2]

After sorting:

[1, 2, 2]

Start with:

path = []

Record:

[]

Choose 1:

path = [1]

Record:

[1]

From here, choose the first 2:

path = [1, 2]

Record:

[1, 2]

Choose the second 2 deeper:

path = [1, 2, 2]

Record:

[1, 2, 2]

Backtrack to:

path = [1]

At the same level, the second 2 is skipped because it would create another [1, 2].

Backtrack to:

path = []

Choose the first 2:

path = [2]

Record:

[2]

Then choose the second 2 deeper:

path = [2, 2]

Record:

[2, 2]

At the top level, the second 2 is skipped.

Final answer:

[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

Correctness

The algorithm records path at every recursive call. Since path is formed by choosing elements from increasing indices, every recorded path is a valid subset of nums.

Sorting places equal values next to each other. At each recursion level, the loop tries possible next values from left to right. If nums[i] == nums[i - 1] and i > start, then choosing nums[i] as the next value would produce the same subsets as choosing nums[i - 1] as the next value at that same level. Skipping it prevents duplicate subsets.

The algorithm still allows duplicates when they are chosen at different recursion depths. For example, it can choose the first 2, recurse, then choose the second 2, producing [2, 2]. So valid subsets that need repeated values are not lost.

Every unique subset can be represented by choosing some count of each distinct value. Because the sorted array groups equal values together, the algorithm can choose the first c copies of a value to represent choosing that value c times. Therefore, every unique subset has one valid path in the recursion.

Thus the algorithm generates every unique subset exactly once.

Complexity

Let:

n = len(nums)

There can be up to 2^n unique subsets when all values are distinct.

Copying each subset can cost up to O(n).

Sorting costs O(n log n), which is dominated by O(n * 2^n) for subset generation.

Implementation

class Solution:
    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        nums.sort()

        ans = []
        path = []

        def backtrack(start: int) -> None:
            ans.append(path.copy())

            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue

                path.append(nums[i])
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return ans

Code Explanation

Sort first so duplicate values are adjacent:

nums.sort()

The result list is:

ans = []

The current subset is:

path = []

At every recursive call, record the current subset:

ans.append(path.copy())

This is correct because every partial path is itself a valid subset.

Then try every possible next element:

for i in range(start, len(nums)):

Skip duplicate choices at the same recursion level:

if i > start and nums[i] == nums[i - 1]:
    continue

Choose the current number:

path.append(nums[i])

Recurse using only later indices:

backtrack(i + 1)

Undo the choice:

path.pop()

Finally, return all recorded subsets.

Testing

Because LeetCode accepts any order, normalize the result before comparing.

def normalize(result):
    return sorted(tuple(row) for row in result)

def run_tests():
    s = Solution()

    assert normalize(s.subsetsWithDup([1, 2, 2])) == normalize([
        [],
        [1],
        [1, 2],
        [1, 2, 2],
        [2],
        [2, 2],
    ])

    assert normalize(s.subsetsWithDup([0])) == normalize([
        [],
        [0],
    ])

    assert normalize(s.subsetsWithDup([1, 1])) == normalize([
        [],
        [1],
        [1, 1],
    ])

    assert normalize(s.subsetsWithDup([2, 1, 2])) == normalize([
        [],
        [1],
        [1, 2],
        [1, 2, 2],
        [2],
        [2, 2],
    ])

    assert normalize(s.subsetsWithDup([1, 1, 1])) == normalize([
        [],
        [1],
        [1, 1],
        [1, 1, 1],
    ])

    print("all tests passed")

run_tests()

Test meaning: