LeetEye LeetEye
Hard Backtracking ~5 min

Subsets

backtracking subsets

Problem

Given an integer array nums of unique elements, 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,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2
Input: nums = [0]
Output: [[],[0]]
Key Insight

For each element, make a binary choice: include it or not.

For each element: include or skip. Process in order (start index) to avoid duplicates. Backtrack after each choice.

How to Approach This Problem

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

Step-by-Step Reasoning

1 For n elements, the total number of subsets is:
Answer: 2^n
Each element is either in or out. 2 choices x n elements = 2^n subsets.
2 The empty set [] is:
Answer: Always a valid subset
Every set has an empty subset (choosing to include nothing).
3 At element nums[i], we:
Answer: Either include or exclude it
Both choices lead to valid subsets. We explore both paths.
4 We add the current subset to results:
Answer: At every decision point
Every state is a valid subset. We add current subset at each recursive call.
5 To avoid duplicate subsets like [1,2] and [2,1]:
Answer: Always process in increasing index order
By only considering elements at index >= current, we avoid revisiting earlier elements.

Solution

def subsets(nums: List[int]) -> List[List[int]]:
    result = []
    
    def backtrack(start, current):
        result.append(current[:])
        
        for i in range(start, len(nums)):
            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