LeetCode · #90

Subsets II Solution

Given an integer array nums that may contain duplicates, return all possible subsets without duplicate subsets.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #90

🏗️

Pattern

Backtracking — sort + same-level dedup

This is the duplicate-aware version of Subsets. We still want the full power set, but repeated values in the input must not produce repeated subsets in the output.

Example

Input: nums = [1,2,2]
Output: [[],[1],[2],[1,2],[2,2],[1,2,2]]
// [1,2] appears once, not twice.

Constraints

• 1 ≤ nums.length ≤ 10 • -10 ≤ nums[i] ≤ 10

Section Two · Approach 1

Generate All + Deduplicate

Generate every subset as if all values were unique, but normalize each subset and store it in a set so duplicates collapse into one entry.

Problem: This works, but it spends time generating duplicate subsets first and only removes them afterward. We can avoid creating duplicates at all by sorting and skipping repeated values at the same recursion depth.

Java — Deduplicate with a set

 import java.util.*;
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
Set<List<Integer>> set = new LinkedHashSet<>();
dfs(nums, 0, new ArrayList<>(), set);
return new ArrayList<>(set);
    }
private void dfs(int[] nums, int i,
List<Integer> path,
Set<List<Integer>> set) {
if (i == nums.length) {
            set.add(new ArrayList<>(path));
return;
        }
        path.add(nums[i]);
dfs(nums, i + 1, path, set);
        path.remove(path.size() - 1);
dfs(nums, i + 1, path, set);
    }
}

Python — Deduplicate with a set

 class Solution:
def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        seen = set()
def dfs(i: int, path: list[int]) -> None:
if i == len(nums):
                seen.add(tuple(path))
return
path.append(nums[i])
dfs(i + 1, path)
            path.pop()
dfs(i + 1, path)
dfs(0, [])
return [list(t) for t in seen]

Metric	Value
Time	O(n · 2ⁿ)
Space	O(n · 2ⁿ)

Section Three · Approach 2

Backtracking with Sort + Skip

Sort the array first. Then, while exploring choices from left to right, skip a value if it equals the previous one and both are being considered at the same recursion depth. This prevents duplicate subsets from ever being generated.

💡 Mental model: Imagine identical books on a shelf. At one decision level, taking the first copy of book “2” or the second copy as the starting pick creates the same subset shape. So at that same shelf level, you pick only the first identical copy and skip the rest. Deeper recursion is different, because choosing the second copy after already choosing the first gives subsets like [2,2], which are valid and distinct.

Algorithm

Sort nums so duplicates sit next to each other.
Add the current path to the answer at every node.
Loop from start onward.
If i > start && nums[i] == nums[i-1], skip it — same value at same level.
Recurse with i + 1 because subsets do not reuse indices.

🎯 Key invariant: i > start means “same recursion level.” That condition is what prevents duplicates without blocking valid deeper subsets like [2,2].

Section Four · Trace

Visual Walkthrough

Trace for nums = [1,2,2] after sorting:

Skip duplicate 2 only at the same level

Section Five · Implementation

Code — Java & Python

Java — Sort + skip duplicates

 import java.util.*;
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), res);
return res;
    }
private void backtrack(int[] nums, int start,
List<Integer> path,
List<List<Integer>> res) {
        res.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) continue;
            path.add(nums[i]);
backtrack(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }
}

Python — Sort + skip duplicates

 class Solution:
def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        res = []
def backtrack(start: int, path: list[int]) -> None:
            res.append(path[:])
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)
                path.pop()
backtrack(0, [])
return res

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Generate-all + set	O(n · 2ⁿ)	O(n · 2ⁿ)	Simple but creates duplicates first
Sort + skip ← optimal	O(n · 2ⁿ)	O(n · 2ⁿ)	Avoids duplicate branches entirely

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
All same	`[2,2,2]`	Answer should be [], [2], [2,2], [2,2,2].
No duplicates	`[1,2,3]`	Behaves exactly like LC 78.
Single element	`[0]`	Only [] and [0].
Negative values	`[-1,-1]`	Sorting and dedup logic still works.

⚠ Common Mistake: Writing if (nums[i] == nums[i-1]) continue; without checking i > start. That incorrectly skips valid deeper choices and loses subsets like [2,2].

← Back to Backtracking problems

LearningTree

LC 90 · Subsets II — Solution & Explanation | DSA Guide