Will the Guru

Backtracking is a method that removes child nodes that will not satisfy the condition and go back to parent node to proceed to other child nodes. Usually backtracking is related with DFS, which searches through all the children nodes.

Typically, problems that require “Print all” or “Get all” are the ones that need backtracking technique to solve.

Pseudo code

1. Recursive backtracking solution

void solve(n, other params) : 
    if (found a solution) :
        solutionsFound = solutionsFound + 1;
        displaySolution();
        if (solutionsFound >= solutionTarget) : 
            System.exit(0);
        return;

    for (val = first to last) :
        if (isValid(val, n)) :
            applyValue(val, n);
            solve(n+1, other params); // other params should include the result of applyValue()
            removeValue(val, n);

if we don’t allow using the same node multiple times, iteration should start from the passed index

void solve(n, other params, idx) :
    if (found a solution) :
        solutionsFound = solutionsFound + 1;
        displaySolution();
        if (solutionsFound >= solutionTarget) : 
            System.exit(0);
        return

    for (val = idx to last) :
        if (isValid(val, n)) :
            applyValue(val, n);
            solve(n+1, other params, idx+1); // other params should include the result of applyValue()
            removeValue(val, n);

2. Finding whether solution exists or not

boolean solve(n, other params) :
    if (found a solution) :
        displaySolution();
        return true;

    for (val = first to last) :
        if (isValid(val, n)) :
            applyValue(val, n);
            if (solve(n+1, other params)) // other params should include the result of applyValue()
                return true;
            removeValue(val, n);
        return false;

Exercises

• https://leetcode.com/problems/permutations/
• https://www.acmicpc.net/problem/14888
• https://www.acmicpc.net/problem/6603
• https://www.acmicpc.net/step/34

• Solutions
  • https://github.com/youngkih/algorithm-problems

Reference

• https://www.geeksforgeeks.org/backtracking-introduction/
• https://mygumi.tistory.com/191