📔
Algorithms Analysis & Design
  • Algorithm Analysis & Design
  • 🚢Searching and Sorting
    • Introduction-Search
    • Linear Search
    • Binary Search
    • Interpolation Search
    • Introduction-Sorting
    • Bubble Sort
    • Selection Sort
    • Counting Sort
  • 💸Greedy Method
    • Introduction
    • Activity Selection
    • Fractional Knapsack Problem
    • Graph Colouring
  • 🚠Backtracking
    • Introduction
    • Hamiltonian Path/Cycle Problem
    • N Queen Problem
    • Rat in a Maze
    • Knight's Tour Problem
  • ⚔️Divide and Conquer
    • Introduction
    • Strassen's Matrix multiplication
    • Karatsuba algorithm
    • Tower of Hanoi
    • Closest Pair
  • 💣Dynamic Programming
    • Introduction
    • Longest Common Subsequence
    • Floyd-Warshall Algorithm
    • 0-1 Knapsack problem
    • Dice Throw
  • 📈Graph
    • Introduction
    • DFS
    • Dictionary Game
    • BFS
    • Flood Fill Algorithm
    • Minesweeper Lite
  • 🔢Number Theory
    • Introduction
    • GCD
    • Factorial
    • IsPrime | School Method
    • IsPrime | Fermat's Little Theorem
    • IsPrime | Miller-Rabin Method
  • 🌮References
Powered by GitBook
On this page
  • State Space Tree
  • Backtracking Algorithm
  • Example Backtracking Approach

Was this helpful?

  1. Backtracking

Introduction

PreviousGraph ColouringNextHamiltonian Path/Cycle Problem

Last updated 3 years ago

Was this helpful?

A backtracking algorithm is a problem-solving algorithm that uses a brute force approach for finding the desired output.

The brute force strategy tests all alternative solutions before selecting the desired/best one. Backtracking implies that if the present answer isn't working, you should go back and try something else.

As a result, recursion is employed in this method. When there are several solutions to a problem, this method is utilised to solve it.

State Space Tree

A space state tree is a tree representing all the possible states (solution or nonsolution) of the problem from the root as an initial state to the leaf as a terminal state.

State Space Tree

Backtracking Algorithm

Backtrack(x)
    if x is not a solution
        return false
    if x is a new solution
        add to list of solutions
    backtrack(expand x)

Example Backtracking Approach

Problem: You want to find all the possible ways of arranging 2 boys and 1 girl on 3 benches. Constraint: Girl should not be on the middle bench.

Solution: There are a total of 3! = 6 possibilities. We will try all the possibilities and get the possible solutions. We recursively try all the possibilities.

All the possibilities are:

The following state space tree shows the possible solutions.

All the possibilities

State tree with all the solutions

🚠
State state tree
State Space Tree
All the possibilities