LeetCode 90 - Subsets II

LeetCode Problem 90

Difficulty: 🟡 Medium
Topics: Array, Backtracking, Bit Manipulation

Solution

Problem Understanding

The problem asks us to generate every possible subset of a given integer array. A subset is any selection of elements from the array, including the empty subset and the subset containing all elements.

Unlike the classic Subsets problem, this version introduces an important complication: the input array may contain duplicate values. Because of this, multiple different selection paths could produce the same subset. The final result must contain only unique subsets.

For example, if the input is [1,2,2], the subset [2] can be formed using either the first 2 or the second 2. Even though these come from different indices, they represent the same subset and should appear only once in the output.

The input array length is at most 10, which is relatively small. Since every element can either be included or excluded, the total number of possible subsets is inherently exponential. In fact, even without duplicates, an array of length n has 2^n subsets. Because the constraints are small, exponential algorithms are acceptable, but we still need a strategy that avoids generating duplicate subsets repeatedly.

The important challenge is not generating subsets, but generating them uniquely.

Several edge cases are especially important:

• Arrays containing many duplicates, such as [2,2,2], can easily produce repeated subsets if duplicates are not handled carefully.
• Arrays with only one element, such as [0], should still correctly produce both the empty subset and the singleton subset.
• Arrays with negative numbers must work exactly the same way as positive numbers because subset generation depends only on positions and equality.
• The empty subset must always be included.
• Since the problem guarantees at least one element, we do not need to handle an empty input array, although the algorithm would naturally support it.

Approaches

Brute Force Approach

A straightforward solution is to generate every possible subset using binary masks or recursive inclusion/exclusion.

For an array of length n, there are 2^n possible combinations. We can generate all subsets and store them in a set structure to remove duplicates afterward.

For example, with [1,2,2], we could generate:

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

Then we could convert each subset into a tuple and insert it into a hash set to eliminate duplicates.

This works because sets automatically enforce uniqueness. However, it is inefficient because duplicate subsets are still generated and processed before being removed.

Key Insight for the Optimal Solution

The key observation is that duplicate subsets arise only when duplicate numbers are processed independently in the same recursive level.

If we sort the array first, duplicate values become adjacent. Then during backtracking, whenever we encounter a duplicate value at the same recursion depth, we skip it.

For example, after sorting [1,2,2]:

• At one recursion level, we choose the first 2
• When we reach the second 2 at the same level, we skip it because it would generate identical subsets

This avoids creating duplicates in the first place, which is more efficient and cleaner than generating everything and deduplicating afterward.

The algorithm therefore combines:

• Sorting
• Backtracking
• Duplicate skipping

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n × n)	O(2^n × n)	Generates all subsets, then removes duplicates using a set
Optimal	O(2^n × n)	O(2^n × n)	Avoids duplicate generation during backtracking

Although both approaches have exponential complexity, the optimal solution avoids redundant work and is the intended interview solution.

Algorithm Walkthrough

1. Sort the input array.

Sorting groups duplicate values together. This is essential because it allows us to detect duplicates easily during recursion.

Example:

[2,1,2] -> [1,2,2]

2. Initialize the result list.

We will store every unique subset inside this list. 3. Start a backtracking function.

The recursive function needs:

• The current starting index
• The current subset being built

4. Add the current subset to the result.

Every recursive state represents a valid subset. Even the empty subset is valid. 5. Iterate through remaining elements starting from the current index.

For each position:

• Choose the current number
• Add it to the subset
• Recurse forward
• Remove it afterward to backtrack

6. Skip duplicate elements at the same recursion depth.

This is the most important step.

During iteration, if:

i > start and nums[i] == nums[i - 1]

then skip the current element.

The condition i > start ensures we skip duplicates only within the same recursive level, not across deeper recursive branches. 7. Continue recursion until all possibilities are explored.

Since each recursive call advances the starting index, every subset is generated exactly once.

Why it works

Sorting ensures duplicates are adjacent. During recursion, the duplicate-skipping condition prevents the algorithm from exploring equivalent branches that would generate identical subsets.

Each recursive level represents choosing the next element for the subset. By allowing only the first occurrence of a duplicated value at a given level, every unique subset is generated exactly once.

Python Solution

from typing import List

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        
        result = []
        subset = []

        def backtrack(start: int) -> None:
            result.append(subset[:])

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

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

        backtrack(0)

        return result

The implementation begins by sorting the input array so duplicate values become adjacent. This allows the duplicate-skipping logic to work correctly.

The result list stores all valid subsets, while subset tracks the current subset being constructed during recursion.

The backtrack function represents the recursive exploration process. At the start of every call, the current subset is copied into the result list because every recursive state corresponds to a valid subset.

The loop iterates through candidate elements starting from start. Before processing an element, the algorithm checks whether it is a duplicate of the previous value at the same recursion depth. If so, it skips the element to avoid duplicate subsets.

When an element is selected, it is appended to subset, recursion continues with the next index, and afterward the element is removed using pop() to restore the previous state.

The recursive exploration systematically builds all valid unique subsets.

Go Solution

package main

import "sort"

func subsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)

	result := [][]int{}
	subset := []int{}

	var backtrack func(start int)

	backtrack = func(start int) {
		current := make([]int, len(subset))
		copy(current, subset)

		result = append(result, current)

		for i := start; i < len(nums); i++ {
			if i > start && nums[i] == nums[i-1] {
				continue
			}

			subset = append(subset, nums[i])

			backtrack(i + 1)

			subset = subset[:len(subset)-1]
		}
	}

	backtrack(0)

	return result
}

The Go implementation follows the same recursive logic as the Python solution.

One important Go-specific detail is copying slices before appending them to the result. Slices reference shared underlying arrays, so directly appending subset would cause later modifications to affect previously stored subsets. To avoid this, the implementation creates a new slice and copies the current subset into it before storing it.

Backtracking is handled using slice resizing:

subset = subset[:len(subset)-1]

This removes the last element efficiently.

No special handling for nil versus empty slices is required because the algorithm naturally produces the empty subset as the first result.

Worked Examples

Example 1

Input:

nums = [1,2,2]

After sorting:

[1,2,2]

Recursive Trace

Step	Current Subset	Start Index	Action
1	[]	0	Add empty subset
2	[1]	1	Include 1
3	[1,2]	2	Include first 2
4	[1,2,2]	3	Include second 2
5	[1,2]	2	Backtrack
6	[1]	1	Backtrack
7	[1]	1	Skip duplicate 2
8	[]	0	Backtrack
9	[2]	2	Include first 2
10	[2,2]	3	Include second 2
11	[2]	2	Backtrack
12	[]	0	Backtrack
13	[]	0	Skip duplicate 2

Final result:

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

Example 2

Input:

nums = [0]

Recursive Trace

Step	Current Subset	Start Index	Action
1	[]	0	Add empty subset
2	[0]	1	Include 0
3	[0]	1	Backtrack

Final result:

[
    [],
    [0]
]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(2^n × n)	There are up to 2^n subsets, and copying each subset takes O(n) time
Space	O(2^n × n)	Output storage dominates because all subsets must be stored

The recursion depth is at most n, so the auxiliary recursion stack uses O(n) space. However, the result itself contains exponentially many subsets, which dominates the total memory usage.

Even with duplicate skipping, the worst case still occurs when all elements are unique, producing 2^n subsets.

Test Cases

from typing import List

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        
        result = []
        subset = []

        def backtrack(start: int) -> None:
            result.append(subset[:])

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

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

        backtrack(0)

        return result

solution = Solution()

# Example 1
assert sorted(solution.subsetsWithDup([1,2,2])) == sorted([
    [],
    [1],
    [1,2],
    [1,2,2],
    [2],
    [2,2]
])  # basic duplicate handling

# Example 2
assert sorted(solution.subsetsWithDup([0])) == sorted([
    [],
    [0]
])  # single element

# All duplicates
assert sorted(solution.subsetsWithDup([2,2,2])) == sorted([
    [],
    [2],
    [2,2],
    [2,2,2]
])  # repeated identical values

# No duplicates
assert sorted(solution.subsetsWithDup([1,2,3])) == sorted([
    [],
    [1],
    [2],
    [3],
    [1,2],
    [1,3],
    [2,3],
    [1,2,3]
])  # classic subsets case

# Negative numbers
assert sorted(solution.subsetsWithDup([-1,-1,2])) == sorted([
    [],
    [-1],
    [-1,-1],
    [2],
    [-1,2],
    [-1,-1,2]
])  # handles negatives correctly

# Mixed duplicates
assert sorted(solution.subsetsWithDup([1,2,2,3])) == sorted([
    [],
    [1],
    [2],
    [2,2],
    [3],
    [1,2],
    [1,2,2],
    [1,3],
    [2,3],
    [2,2,3],
    [1,2,3],
    [1,2,2,3]
])  # multiple branching paths

print("All tests passed!")

Test Case Summary

Test	Why
[1,2,2]	Validates duplicate skipping
[0]	Smallest valid input
[2,2,2]	Ensures repeated duplicates are handled correctly
[1,2,3]	Verifies standard subset generation
[-1,-1,2]	Confirms negative numbers work properly
[1,2,2,3]	Tests more complex duplicate branching

Edge Cases

Arrays Containing Only Duplicates

An input like [2,2,2] is a common source of bugs because naive recursive algorithms may generate the same subset many times.

Without duplicate skipping, subsets such as [2] and [2,2] would appear repeatedly. The implementation prevents this by skipping duplicate values at the same recursion level.

As a result, the algorithm correctly produces:

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

with no duplicates.

Arrays With No Duplicates

When all elements are unique, such as [1,2,3], the problem reduces to the standard subsets problem.

The duplicate-skipping condition never triggers because adjacent elements are different after sorting. The algorithm therefore explores every possible inclusion/exclusion combination normally.

This verifies that the duplicate handling does not interfere with standard subset generation.

Single Element Arrays

Inputs like [0] test the smallest valid problem size.

The algorithm must still include both the empty subset and the subset containing the element itself.

Because the recursive function immediately records the current subset before exploring further choices, the empty subset is naturally included. Then recursion correctly generates [0].

This confirms the algorithm handles minimal inputs cleanly without requiring special-case logic.