Backtracking Patterns

🧭 Backtracking Patterns: The Adventure of Trying Every Path

Imagine you’re in a magical maze. You want to find treasure at the end. But there are many paths! Some lead to dead ends, some lead to treasure.

What do you do?

You try one path. If it works, great! If it hits a wall, you go back and try another path. This “going back” is called Backtracking.

🎯 The Big Idea

Backtracking is like being a brave explorer who:

1. Tries a path
2. Checks if it leads somewhere good
3. If stuck, goes back and tries a different path
4. Keeps doing this until finding the treasure (or trying everything)

1. Backtracking Fundamentals

What Is Backtracking?

Think of building a tower with blocks. You add one block at a time. If the tower starts to wobble, you remove the last block and try a different one.

The Recipe:

1. Choose - Pick an option
2. Explore - See where it leads
3. Unchoose - If stuck, remove that choice and try another

Simple Example: Finding a Path

function explore(position, path) {
  // Base case: Found treasure!
  if (position === 'treasure') {
    console.log('Found it!', path);
    return true;
  }

  // Base case: Dead end
  if (position === 'wall') {
    return false;
  }

  // Try each direction
  for (let direction of ['left', 'right']) {
    path.push(direction);      // Choose

    let nextPos = move(position, direction);
    if (explore(nextPos, path)) {
      return true;             // Explore worked!
    }

    path.pop();                // Unchoose (backtrack)
  }

  return false;
}

Key Pattern:

• Push something onto your path (choose)
• Try it out (explore)
• Pop it off if it didn’t work (unchoose)

2. Backtracking with Pruning

What Is Pruning?

Imagine you know the treasure is NOT behind red doors. Would you waste time opening red doors? No!

Pruning means skipping paths you already know won’t work. It’s like being a smart explorer who doesn’t walk into dead ends.

Example: Find Numbers That Add to 10

function findSum(target, start, current, path) {
  // Found it!
  if (current === target) {
    console.log(path);
    return;
  }

  // PRUNING: Already too big? Stop!
  if (current > target) {
    return;  // Don't explore further
  }

  for (let i = start; i <= target; i++) {
    path.push(i);
    findSum(target, i, current + i, path);
    path.pop();
  }
}

The Magic: We stop early when current > target. No point adding more numbers if we’re already over!

graph TD
    A["Start: sum=0"] --> B{sum > target?}
    B -->|Yes| C["✂️ PRUNE - Stop here!"]
    B -->|No| D["Try next number"]
    D --> E{sum = target?}
    E -->|Yes| F["🎉 Found solution!"]
    E -->|No| A

3. Permutations

What Are Permutations?

If you have 3 colored blocks: 🔴🟢🔵

Permutations = All the different ways to arrange them in a line.

• 🔴🟢🔵
• 🔴🔵🟢
• 🟢🔴🔵
• 🟢🔵🔴
• 🔵🔴🟢
• 🔵🟢🔴

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

The Code

function permute(nums) {
  let results = [];

  function backtrack(current, remaining) {
    // No more to arrange? Done!
    if (remaining.length === 0) {
      results.push([...current]);
      return;
    }

    // Try each remaining number first
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);

      // Remove this number from remaining
      let newRemaining = [
        ...remaining.slice(0, i),
        ...remaining.slice(i + 1)
      ];

      backtrack(current, newRemaining);
      current.pop();  // Backtrack!
    }
  }

  backtrack([], nums);
  return results;
}

// Example: permute([1, 2, 3])
// Returns all 6 arrangements!

4. Combinations

What Are Combinations?

You have 4 candies: 🍬🍭🍫🍩

You can only pick 2 candies. How many different pairs?

• 🍬🍭
• 🍬🍫
• 🍬🍩
• 🍭🍫
• 🍭🍩
• 🍫🍩

That’s 6 combinations!

Key Difference from Permutations:

• Permutations: Order matters (🔴🟢 ≠ 🟢🔴)
• Combinations: Order doesn’t matter (🍬🍭 = 🍭🍬)

The Code

function combine(n, k) {
  let results = [];

  function backtrack(start, current) {
    // Got enough items? Save it!
    if (current.length === k) {
      results.push([...current]);
      return;
    }

    // Try each number from start to n
    for (let i = start; i <= n; i++) {
      current.push(i);
      backtrack(i + 1, current);  // Start from i+1
      current.pop();
    }
  }

  backtrack(1, []);
  return results;
}

// combine(4, 2) gives:
// [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

The Secret: We use i + 1 so we never pick the same item twice!

5. Subsets Generation

What Are Subsets?

You have a toy box with toys: 🚗🎸🎨

Subsets = All possible groups you could make (including none and all):

• [] (empty - no toys)
• [🚗]
• [🎸]
• [🎨]
• [🚗, 🎸]
• [🚗, 🎨]
• [🎸, 🎨]
• [🚗, 🎸, 🎨]

That’s 8 subsets! (2³ = 8)

The Code

function subsets(nums) {
  let results = [];

  function backtrack(index, current) {
    // Every state is a valid subset!
    results.push([...current]);

    // Try adding each remaining number
    for (let i = index; i < nums.length; i++) {
      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop();
    }
  }

  backtrack(0, []);
  return results;
}

// subsets([1, 2, 3])
// Returns: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

graph TD
    A["Start: []"] --> B["Add 1: [1]"]
    A --> C["Skip 1"]
    B --> D["Add 2: [1,2]"]
    B --> E["Skip 2: [1]"]
    D --> F["Add 3: [1,2,3]"]
    D --> G["Skip 3: [1,2]"]
    C --> H["Add 2: [2]"]
    C --> I["Skip 2: []"]

6. Combination Sum

The Problem

You have coins: [2, 3, 5]

Can you make exactly 8 using any coins? (You can use same coin many times!)

Answer: Yes!

• 2 + 2 + 2 + 2 = 8 ✅
• 3 + 3 + 2 = 8 ✅
• 5 + 3 = 8 ✅

The Code

function combinationSum(candidates, target) {
  let results = [];

  function backtrack(start, current, sum) {
    // Perfect! Found target
    if (sum === target) {
      results.push([...current]);
      return;
    }

    // Too much? Stop (pruning!)
    if (sum > target) {
      return;
    }

    for (let i = start; i < candidates.length; i++) {
      current.push(candidates[i]);
      // Use 'i' not 'i+1' - can reuse same number!
      backtrack(i, current, sum + candidates[i]);
      current.pop();
    }
  }

  backtrack(0, [], 0);
  return results;
}

Key Insight: We pass i (not i + 1) because we CAN use the same number again!

7. Palindrome Partitioning

What Is a Palindrome?

A word that reads the same forwards and backwards:

• “mom” ✅
• “racecar” ✅
• “hello” ❌

The Challenge

Split “aab” so every piece is a palindrome:

• [“a”, “a”, “b”] ✅ (each letter is a palindrome)
• [“aa”, “b”] ✅ (“aa” reads same both ways)

The Code

function partition(s) {
  let results = [];

  function isPalindrome(str) {
    return str === str.split('').reverse().join('');
  }

  function backtrack(start, current) {
    // Used all letters? Save it!
    if (start === s.length) {
      results.push([...current]);
      return;
    }

    // Try every possible substring
    for (let end = start + 1; end <= s.length; end++) {
      let substring = s.slice(start, end);

      // Only continue if it's a palindrome
      if (isPalindrome(substring)) {
        current.push(substring);
        backtrack(end, current);
        current.pop();
      }
    }
  }

  backtrack(0, []);
  return results;
}

// partition("aab")
// Returns: [["a","a","b"], ["aa","b"]]

8. Generate Parentheses

The Problem

Make all valid combinations of 3 pairs of parentheses:

((()))  ✅
(()())  ✅
(())()  ✅
()(())  ✅
()()()  ✅

Invalid examples:

)()(    ❌ (starts with closing)
(()))   ❌ (unbalanced)

The Rules

1. Never more closing ) than opening (
2. Total opening = Total closing = n

The Code

function generateParenthesis(n) {
  let results = [];

  function backtrack(current, open, close) {
    // Done? Save it!
    if (current.length === 2 * n) {
      results.push(current);
      return;
    }

    // Can add more '('?
    if (open < n) {
      backtrack(current + '(', open + 1, close);
    }

    // Can add ')' only if we have unmatched '('
    if (close < open) {
      backtrack(current + ')', open, close + 1);
    }
  }

  backtrack('', 0, 0);
  return results;
}

// generateParenthesis(3) returns all 5 valid combinations

graph TD
    A["'' open:0 close:0"] --> B["'#40;' open:1"]
    B --> C["'((' open:2"]
    B --> D["'#40;#41;' close:1"]
    C --> E["'((#40;' open:3"]
    C --> F["'((#41;' close:1"]
    E --> G["'((#40;#41;' close:1"]
    G --> H["'((#40;#41;'"]
    H --> I["'((#40;))#41;'"]

🎯 The Master Pattern

Every backtracking problem follows this template:

function backtrack(state) {
  // 1. Check if we found a solution
  if (isSolution(state)) {
    saveSolution(state);
    return;
  }

  // 2. Optional: Prune if not worth exploring
  if (shouldPrune(state)) {
    return;
  }

  // 3. Try all possible choices
  for (let choice of getChoices(state)) {
    makeChoice(choice);      // Choose
    backtrack(newState);     // Explore
    undoChoice(choice);      // Unchoose
  }
}

🚀 Quick Reference

💡 Remember

Backtracking is just:

1. Try something
2. Check if it works
3. Undo if it doesn’t
4. Repeat with next option

You’re a brave explorer in a maze. Try paths, go back when stuck, and keep exploring until you find ALL the treasures!

🎉 You’ve got this!