Backtracking Basics 10 XP Easy

Ctrl+Enter Run Ctrl+S Save

Backtracking is like exploring a maze — try a path, if it's a dead end, go back and try another path! 🏰

💡 Think of it like this: You're in a maze with many forks. At each fork, you pick a direction and walk. If you hit a wall, you backtrack to the last fork and try a different direction. You keep exploring until you find the exit (or try ALL paths).

The Backtracking Template (memorize this!):

def backtrack(state, choices):
    if is_solution(state):       # Found a valid answer?
        results.append(state[:]) # Save a COPY
        return
    
    for choice in choices:
        if is_valid(choice):     # Can we make this choice?
            state.append(choice)      # 1. CHOOSE
            backtrack(state, ...)     # 2. EXPLORE
            state.pop()               # 3. UN-CHOOSE (backtrack!)

The three key steps:

✅ Choose: Add an element to the current path
🔍 Explore: Recurse to see what we can build from here
↩️ Un-choose: Remove the element (go back to try something else)

💭 Now it's your turn! Using the approach above, implement your solution in the editor. You've got this! 💪

Classic backtracking problems: Subsets, Permutations, Combination Sum, N-Queens, Word Search, Sudoku Solver. Master the template above and you can solve them all!

📋 Instructions

Generate all subsets of [1, 2, 3] using backtracking. Print number of subsets.

Start with empty path. At each level, choose to include or exclude the current element. When index == len(nums), add path to result.

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

# Example: Generate all subsets of [1, 2, 3]
def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(path[:])           # Every path is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])         # Choose
            backtrack(i + 1, path)        # Explore
            path.pop()                    # Un-choose
    backtrack(0, [])
    return result
# Returns: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

🧪 Test Cases

Input

len(subsets([1, 2, 3]))

Expected

8

Test case 1

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›