Subsets 20 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

This is LeetCode #78: Subsets — the fundamental backtracking problem! 🎒

💡 Think of it like this: You're packing a bag and you have 3 items. For each item, you have 2 choices: put it in or leave it out. That means 2×2×2 = 8 possible combinations!

# Input:  nums = [1, 2, 3]
# Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]
# That's all 2^3 = 8 possible subsets!

The Decision Tree: For each number, we make a choice — include it or not:

#                    []
#                 /      \
#           include 1   skip 1
#             [1]         []
#            /   \       /   \
#        inc 2  skip 2  inc 2  skip 2
#         [1,2]  [1]    [2]    []
#         ...    ...     ...    ...

The Backtracking Template:

💭 Your turn! Take what you learned above and write the code yourself. Struggling is part of learning! 🧠

Key backtracking concepts:

✅ Choose — add an element to the current path
🔍 Explore — recurse deeper
↩️ Un-choose — remove the element (go back = backtrack!)
This pattern works for Subsets, Permutations, Combinations, N-Queens, and more!

Complexity: Time O(n × 2ⁿ) — 2ⁿ subsets, each up to length n. Space O(n) for recursion depth.

📋 Instructions

Generate all subsets of [1,2,3]. Print them sorted.

Backtracking template: for each index from start to end, include the number, recurse with i+1, then remove the number (backtrack). Add current subset to result at each step.

⚠️ Try solving it yourself first — you'll learn more!

def subsets(nums):
    result = []
    
    def backtrack(start, current):
        result.append(current[:])  # Add a COPY of current subset
        
        for i in range(start, len(nums)):
            current.append(nums[i])    # Choose
            backtrack(i + 1, current)   # Explore
            current.pop()               # Un-choose (backtrack!)
    
    backtrack(0, [])
    return result

🧪 Test Cases

Input

Run your code

Expected

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

Expected output (8 lines)

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›