Backtracking

Backtracking 回溯法

Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be not a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step, i.e. backtracks and then try again.

Pseudo code for backtracking algorithm

Pick a starting point.
while(Problem is not solved)
    For each path from the starting point.
        check if selected path is safe, if yes select it
        and make recursive call to rest of the problem
        before which undo the current move.
    End For
If none of the move works out, return false, NO SOLUTON.

From UPenn CIS:

Backtracking is a form of recursion.

The usual scenario is that you are faced with a number of options, and you must choose one of these. After you make your choice you will get a new set of options; just what set of options you get depends on what choice you made. This procedure is repeated over and over until you reach a final state. If you made a good sequence of choices, your final state is agoal state;if you didn't, it isn't.

From Harvard FAS Computer Science S-111:

Recursion Revisited; Recursive Backtracking

Template for Recursive Backtracking

// n is the number of the variable that the current
// call of the method is responsible for
boolean findSolution(int n, possibly other params) {
    if (found a solution) {
        this.displaySolution();
        return true;
    }
    // loop over possible values for the nth variable
    for (val = first to last) {
        if (this.isValid(val, n)) {
            this.applyValue(val, n);
            if (this.findSolution(n + 1, other params)) {
                return true;
            }
            this.removeValue(val, n);
        }
    }
    return false;
}

Template for Finding Multiple Solutions (up to some target number of solutions)

boolean findSolutions(int n, possibly other params) {
    if (found a solution) {
        this.displaySolution();
        this.solutionsFound++;
        return (this.solutionsFound >= this.target);
    }
    // loop over possible values for the nth variable
    for (val = first to last) {
        if (isValid(val, n)) {
            this.applyValue(val, n);
            if (this.findSolutions(n + 1, other params)) {
                return true;
            }
            this.removeValue(val, n);
        }
    }
    return false;
}

By gigi就是我

Backtracking 基本概念：

Backtracking（回溯算法）也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

应用技巧：

• 回溯法在用来求问题的 所有解 时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。

• 而回溯法在用来求问题的 任一解 时，只要搜索到问题的一个解就可以结束。

Reference

A general approach to backtracking questions: Subsets, Subsets II, Permutations, Combination Sum, Palindrome Partitioning

LeetCode解题笔记：Backtracking类型解题思路 by gigi就是我

Backtracking - UPenn CIS

Constraint Satisfaction Problems - Sharif UT

Recursive Backtracking - Harvard