Faangprep Logo
Log inStart free
Browse curriculum

Backtracking Introduction

Backtracking is a general algorithmic technique that considers searching every possible combination in order to solve a computational problem. It incrementally builds candidates to solutions and abandons a candidate ('backtracks') as soon as it determines that the candidate cannot possibly be completed to a valid solution.

Choose a step, check it against the rule, and un-choose it if nothing follows.

READY

Start
A
B
A1
A2
B1
B2

Depth

0

 

Three moves, over and over: choose, check, un-choose.

Next

Nothing chosen yet. Two options lead out of Start.

Intuition

Imagine you are in a maze. You embrace a path and keep walking. If you hit a dead end, you turn back (backtrack) to the last junction and try a different path. You repeat this until you find the exit.

This 'try and retreat' strategy is the core of backtracking. It is essentially an optimized exhaustice search.

Concept

Core Principles:

  1. Choice: Make a choice from the available options.
  2. Constraint: Check if the choice is valid.
  3. Goal: Check if we reached the solution.
  4. Backtrack: If the choice leads to a dead end, undo the choice and try the next option.

Recursion Tree:
Backtracking algorithms are often visualized as a tree traversal where the root is the initial state, and branches represent choices. Pruning branches that don't lead to a solution optimizes the search.

How it Works

Backtracking algorithms are often visualized as a State Space Tree.

  • Root: Initial state.
  • Branches: Possible choices.
  • Nodes: Partial solutions.
  • Leaf: Final valid solution or dead end.

The algorithm traverses this tree using Depth-First Search (DFS). When a node violates a constraint, the algorithm 'prunes' the subtree rooted at that node (stops exploring it).

Step-by-Step Breakdown

Generic Algorithm:

  1. Start with an empty solution.
  2. Extend the partial solution by adding an element from the candidate set.
  3. Check if the partial solution is valid:
    • Yes: If it's a complete solution, return it. Else, recurse.
    • No: Discard the extension (backtrack).
  4. If all candidates are tried and none work, return failure.

When to Use

Advantages:

  • Guaranteed to find a solution if one exists.
  • Can find all possible solutions (e.g., all N-Queens arrangements).
  • More efficient than brute force due to pruning.

Use Cases:

  • Constraint Satisfaction Problems (Sudoku, N-Queens).
  • Combinatorial Optimization (Knapsack, Traveling Salesman).
  • Generating all permutations or subsets.

When NOT to Use

Disadvantages:

  • Exponential time complexity in worst case (e.g., O(2^N) or O(N!)).
  • Can be slow for large inputs.
  • Recursive implementation can lead to stack overflow for deep trees.

Avoid When:

  • When an optimal solution can be found using greedy or dynamic programming (which are faster).

How to Identify

Keywords: "Find all solutions", "Generate all...", "Possible combinations", "Constraint satisfaction".

Preparing for interviews? This topic is also taught as a pattern:

Introduction to Backtracking

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Minimum Platforms

Next

Subsets

Frequently Asked Questions

What is Backtracking?

A recursive algorithmic approach that builds a solution incrementally and removes (backtracks) any search branch that fails to satisfy the problem constraints.

Choice, Constraint, and Goal?

The three pillars: Choice (the next candidate), Constraint (rules deciding if choice is safe), and Goal (the target condition to reach).

Backtracking vs Brute Force?

Brute Force explores every path. Backtracking uses "Pruning" to stop exploring a branch the moment it violates a constraint, saving massive time.