Backtracking

Definition

Backtracking is a refined “Brute Force” technique. It builds a solution step-by-step. If it realizes the current path cannot lead to a valid solution, it stops immediately, backtracks (goes back to the previous step), and tries a different option.

How it Works

1. Choose: Pick an option.
2. Constraint Check: Is this option valid?
3. Explore: If valid, move to the next step recursively.
4. Un-choose: If you hit a dead end, undo the choice (backtrack) and try the next option.

Real-World Analogy

Walking through a Maze:

You walk down a path. You hit a dead end. You don’t just stand there; you turn around, walk back to the last intersection, and try the other path.

Example

Problem: Generating all permutations of “ABC”.

• Start with A. Next can be B. Next C. (ABC) -> Valid.
• Backtrack to B. Try to put A? Already used.
• Backtrack to start. Try B first…

Code Example (Python)

def permute(nums):
    result = []
   
    def backtrack(path, remaining):
        # Base Case: No numbers left to pick
        if not remaining:
            result.append(path)
            return
       
        for i in range(len(remaining)):
            # Choose: Pick one number
            # Explore: Pass the rest
            backtrack(path + [remaining[i]], remaining[:i] + remaining[i+1:])
           
    backtrack([], nums)
    return result

print(permute([1, 2, 3]))

Complexity Analysis

• Time Complexity: Generally Exponential, e.g., O(N!) for permutations or O(2^N) for subsets.
• Space Complexity: O(N) for the recursion stack.

Use Cases

• Puzzles: Sudoku solvers, N-Queens problem, Crosswords.
• Combinatorics: Generating all passwords, subsets, or arrangements.