Backtracking Patterns

🌳 Backtracking Patterns: The Art of Exploring Every Path

Imagine you’re in a magical maze. You try one path. Dead end? No problem! You walk back and try another. That’s backtracking!

🎯 What is Backtracking?

Think of backtracking like being a treasure hunter in a cave with many tunnels.

You pick a tunnel. Walk forward. If it’s a dead end, you back up and try a different tunnel. You keep doing this until you find the treasure—or explore every single tunnel.

In simple words:

• Try something
• If it doesn’t work, undo it
• Try something else
• Repeat until you win!

def explore(path):
    if found_treasure(path):
        return path  # Yay!

    for choice in all_choices:
        path.append(choice)    # Try it
        result = explore(path)
        if result:
            return result
        path.pop()             # Undo it

    return None  # Dead end

🧩 Backtracking Fundamentals

The Three Magic Steps

Every backtracking solution follows this recipe:

graph TD
    A["1. CHOOSE"] --> B["Pick one option"]
    B --> C["2. EXPLORE"]
    C --> D["Go deeper with that choice"]
    D --> E["3. UNCHOOSE"]
    E --> F["Remove the choice, try another"]
    F --> A

The Template Everyone Uses

def backtrack(current_state):
    # Base case: Are we done?
    if is_complete(current_state):
        save_result(current_state)
        return

    # Try each possible next step
    for choice in get_choices():
        if is_valid(choice):
            make_choice(choice)      # Choose
            backtrack(current_state) # Explore
            undo_choice(choice)      # Unchoose

Real Example: Picking outfits

• Choose: “I’ll wear the red shirt”
• Explore: “What pants go with it?”
• Unchoose: “Nah, let me try the blue shirt instead”

✂️ Backtracking with Pruning

What’s Pruning?

Imagine you’re climbing a tree to find apples. You see a branch with NO leaves. Would you climb it? No! You skip it.

Pruning = Skipping paths that can’t possibly lead to answers.

This makes backtracking MUCH faster!

graph TD
    A["Start"] --> B["Path 1"]
    A --> C["Path 2"]
    A --> D["Path 3 ❌ PRUNE"]
    B --> E["Answer!"]
    C --> F["Dead End"]
    style D fill:#ffcccc
    style E fill:#ccffcc

Pruning in Action

def backtrack_with_pruning(path, target):
    # Pruning: Stop early if impossible
    if sum(path) > target:
        return  # Don't waste time!

    if sum(path) == target:
        print("Found:", path)
        return

    for num in candidates:
        path.append(num)
        backtrack_with_pruning(path, target)
        path.pop()

The Secret: Add if checks to skip bad paths EARLY. The earlier you prune, the faster you go!

🔄 Permutations

What’s a Permutation?

All possible arrangements of items.

If you have letters [A, B, C], permutations are:

• ABC, ACB, BAC, BCA, CAB, CBA

That’s 6 ways (3 × 2 × 1 = 6)

The Story

You have 3 friends: Alice, Bob, Charlie. They need to stand in a line for a photo. How many different lines can they form?

def permutations(nums):
    result = []

    def backtrack(path, remaining):
        # Base: Used all numbers?
        if not remaining:
            result.append(path[:])
            return

        for i, num in enumerate(remaining):
            path.append(num)
            # remaining without this num
            new_remaining = remaining[:i] + remaining[i+1:]
            backtrack(path, new_remaining)
            path.pop()

    backtrack([], nums)
    return result

print(permutations([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], ...]

Visual Flow

graph TD
    A["[ ]"] --> B["[1]"]
    A --> C["[2]"]
    A --> D["[3]"]
    B --> E["[1,2]"]
    B --> F["[1,3]"]
    E --> G["[1,2,3] ✓"]
    F --> H["[1,3,2] ✓"]

🎒 Combinations

What’s a Combination?

Selecting items where ORDER doesn’t matter.

From [1, 2, 3], choose 2:

• {1, 2}, {1, 3}, {2, 3}

Notice: {1, 2} and {2, 1} are the same combination!

Permutation vs Combination

The Code

def combinations(nums, k):
    result = []

    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return

        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)  # i+1 avoids repeats
            path.pop()

    backtrack(0, [])
    return result

print(combinations([1,2,3,4], 2))
# [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

The Trick: We use start to only look at numbers after the current one. This prevents duplicates!

📦 Subsets Generation

What are Subsets?

All possible groups you can make from a set—including the empty group!

From [1, 2]:

• [] (empty)
• [1]
• [2]
• [1, 2]

That’s 4 subsets (2² = 4)

The Story

You’re packing snacks: Apple, Banana. What are all possible snack bags you could bring?

• No snacks
• Just Apple
• Just Banana
• Apple AND Banana

The Code

def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])  # Save every path!

        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Visual Tree

graph TD
    A["[]"] --> B["[1]"]
    A --> C["[2]"]
    A --> D["[3]"]
    B --> E["[1,2]"]
    B --> F["[1,3]"]
    E --> G["[1,2,3]"]
    C --> H["[2,3]"]

💰 Combination Sum

The Problem

Find all combinations of numbers that add up to a target.

You CAN use the same number multiple times!

Example: Target = 7, Candidates = [2, 3, 5]

• [2, 2, 3] ✓
• [2, 5] ✓

The Story

You have coins worth 2, 3, and 5 dollars. How many ways can you make exactly 7 dollars?

The Code

def combination_sum(candidates, target):
    result = []

    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        if remaining < 0:
            return  # Pruning!

        for i in range(start, len(candidates)):
            path.append(candidates[i])
            # Same i: can reuse same number
            backtrack(i, path, remaining - candidates[i])
            path.pop()

    backtrack(0, [], target)
    return result

print(combination_sum([2,3,5], 7))
# [[2,2,3], [2,5]]

Key Insight: We pass i (not i+1) to allow reusing the same number!

🪞 Palindrome Partitioning

What’s a Palindrome?

A word that reads the same forwards and backwards.

• “aba” ✓
• “racecar” ✓
• “abc” ✗

The Problem

Split a string into pieces where every piece is a palindrome.

Example: “aab”

• [“a”, “a”, “b”] ✓
• [“aa”, “b”] ✓

The Code

def partition(s):
    result = []

    def is_palindrome(text):
        return text == text[::-1]

    def backtrack(start, path):
        if start == len(s):
            result.append(path[:])
            return

        for end in range(start + 1, len(s) + 1):
            substring = s[start:end]
            if is_palindrome(substring):
                path.append(substring)
                backtrack(end, path)
                path.pop()

    backtrack(0, [])
    return result

print(partition("aab"))
# [["a","a","b"], ["aa","b"]]

The Logic:

1. Try every possible first cut
2. If that piece is a palindrome, recurse on the rest
3. If not a palindrome, skip it (pruning!)

🎭 Generate Parentheses

The Problem

Generate all valid combinations of n pairs of parentheses.

Example: n = 2

• “(())” ✓
• “()()” ✓

Not valid:

• “())(” ✗
• “)()(” ✗

The Rules

1. Never have more ) than ( at any point
2. Total ( must equal total ) must equal n

The Code

def generate_parentheses(n):
    result = []

    def backtrack(path, open_count, close_count):
        if len(path) == 2 * n:
            result.append("".join(path))
            return

        # Can add ( if we haven't used n yet
        if open_count < n:
            path.append("(")
            backtrack(path, open_count + 1, close_count)
            path.pop()

        # Can add ) if it won't exceed (
        if close_count < open_count:
            path.append(")")
            backtrack(path, open_count, close_count + 1)
            path.pop()

    backtrack([], 0, 0)
    return result

print(generate_parentheses(3))
# ["((()))", "(()())", "(())()", "()(())", "()()()"]

Visual Decision Tree

graph TD
    A["'' #40;0,0#41;"] --> B["#40; #40;1,0#41;"]
    B --> C["(( #40;2,0#41;"]
    B --> D["#40;#41; #40;1,1#41;"]
    C --> E["((#40; #40;3,0#41;"]
    C --> F["((#41; #40;2,1#41;"]
    D --> G["#40;#41;#40; #40;2,1#41;"]

🎯 The Golden Pattern

All backtracking problems share this structure:

def backtrack(state):
    if is_goal(state):
        record(state)
        return

    for choice in choices:
        if is_valid(choice):     # Prune invalid
            make_choice(choice)   # Choose
            backtrack(state)      # Explore
            undo_choice(choice)   # Unchoose

When to Use Backtracking?

🚀 You’ve Got This!

Backtracking is like being a detective exploring every possibility. You try, learn, undo, and try again. With practice, you’ll recognize these patterns instantly!

Remember:

1. Choose → Make a decision
2. Explore → See where it leads
3. Unchoose → Back up and try another

Now go explore those decision trees! 🌳✨