Introduction to Backtracking

Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, and removing those solutions that fail to satisfy the constraints of the problem at any point of time (this is the "backtrack" step).

Think of it as "Smart Brute Force". Instead of blindly generating every possible combination (like a brute force approach might), Backtracking uses pruning to abandon a path as soon as it determines the path cannot lead to a valid solution.

Imagine you need to generate all subsets of an array [1, 2, 3].

• Subset size 0: []
• Subset size 1: [1], [2], [3]
• Subset size 2: [1,2], [1,3], [2,3]
• ...

If you knew the array always had 3 elements, you could write 3 nested for loops. But what if the input array size N is dynamic? You cannot write N nested loops! You need a way to handle dynamic nesting.

A common instinct is to use loops. For N=2, it works:

for i in range(n):
  for j in range(i+1, n):
    print([nums[i], nums[j]])

The Problem: This code is rigid. It can only find subsets of size 2. To find subsets of size 3, you'd need another loop. To find subsets of size N, you'd need N loops. Since N is unknown until runtime, pure iteration fails.

Instead of loops, we visualize the problem as a Decision Tree (or State-Space Tree).

At each step, we make a Choice (e.g., Include 1 vs Exclude 1).
This branching creates a tree structure where:

• Root: Empty set.
• Branches: Decisions.
• Leaves: Valid solutions.

The mantra for Backtracking is:

1. Choose: Make a choice (add an element to your current candidate).
2. Explore: Recursively move to the next state (call the function again).
3. Unchoose (Backtrack): Undo the choice (remove the element) to return to the previous state.

This "Unchoose" step is why it's called Backtracking. It allows you to reuse the same data structure (current_path) for all solutions, saving memory.