LeetEye LeetEye
Hard Backtracking ~5 min

Subsets II

backtracking subsets-ii

Problem

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Examples

Example 1
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2
Input: nums = [0]
Output: [[],[0]]
Key Insight

Sort the array. Skip duplicates at the same decision level.

Sort first. In backtrack loop, skip if nums[i] == nums[i-1] AND i > start. This avoids exploring duplicate branches at the same decision level.

How to Approach This Problem

Pattern Recognition: When you see keywords like subsets ii backtracking, think Backtracking.

Step-by-Step Reasoning

1 Sorting the array helps because:
Answer: Duplicates become adjacent, easy to detect
After sorting, all 2s are together. We can skip consecutive same values.
2 We skip nums[i] if:
Answer: nums[i] == nums[i-1] and i > start
If the previous element at THIS LEVEL was the same, we've already explored that branch.
3 "Same level" means:
Answer: Same iteration of the for loop at current recursion
Within one call to backtrack, we loop through choices. Same-level duplicates happen in THIS loop.
4 The condition i > start (not i > 0) is important because:
Answer: start marks where valid choices begin for this level
At recursion level with start=2, checking i>0 would wrongly skip element at i=2 if it matches i=1.
5 At the first level (start=0), for [1,2,2]:
Answer: We try 1, then only the first 2
First 2 at index 1 is tried. Second 2 at index 2 is skipped (same as previous at same level).
6 After choosing first 2 (at index 1), from [1,2,2]:
Answer: We can still choose the second 2
We moved to a new level (start=2). At THIS level, index 2 is the first choice, so not skipped.

Solution

def subsetsWithDup(nums: List[int]) -> List[List[int]]:
    nums.sort()
    result = []
    
    def backtrack(start, current):
        result.append(current[:])
        
        for i in range(start, len(nums)):
            # Skip duplicates at same level
            if i > start and nums[i] == nums[i-1]:
                continue
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    
    backtrack(0, [])
    return result

Complexity Analysis

Time O(n * 2^n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Backtracking problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye