Subsets

Return all possible subsets of a set of distinct integers.

Pattern

Include/Exclude

This problem follows the Include/Exclude pattern, commonly found in the Backtracking category. Recognizing this pattern is key to solving it efficiently in an interview setting.

Approach

How to Solve It

At each element, either include or exclude it. Recurse on remaining elements.

Key Insight

The 'append then pop' pattern is the core of backtracking — you explore a branch, undo the choice, then try the next option.

Step-by-step

1Start with an empty current subset and index 0
2At each index, make two recursive calls:
3Include the current element and recurse on next index
4Exclude the current element and recurse on next index
5Base case: when index equals array length, add the current subset to results

Pseudocode

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 Complexity

O(n * 2ⁿ)

Space Complexity

O(n)

Master this pattern with YeetCode

Practice Subsets and similar Backtracking problems with flashcards. Build pattern recognition through active recall.

Practice this problem

NextCombination Sum →