n问题和subset问题中，我们探索了每一种可能性。在每一个决策点，我们对每一个可能的选择进行尝试，知道我们穷举了我们所有可能的选择。这样以来时间复杂度就会很高，尤其是如果我们有许多决策点，并且在每一个决策点我们又有许多选择的时候。而在回溯算法中，我们尝试一种选择，如果满足了条件，我们不再进行其他的选择。这种算法的一般的伪代码模式如下：
?
复制代码
?1 bool Solve(configuration conf)
?2 {
?3 ? ? if (no more choice)
?4 ? ? ? ? return (conf is goal state);
?5?
?6 ? ? for (all available choices)
?7 ? ? {
?8 ? ? ? ? try choice c;
?9?
10 ? ? ? ? ok = solve(conf with choice c made);
11 ? ? ? ? if (ok)
12 ? ? ? ? ? ? return true;
13 ? ? ? ? else
14 ? ? ? ? ? ? unmake c;
15 ? ? }
16?
17 ? ? retun false;
18 }
复制代码
?
?
写回溯函数的忠告是：将有关格局configuration的细节从函数中拿出去（这些细节包括，在每一个决策点有哪些选择，做出选择，判断是否成功等等），放到helper函数中，从而使得主体函数尽可能的简洁清晰，这有助我们确保回溯算法的正确性，同时有助于开发和调试。
?
我们先看第一个例子，从permutation问题中变异而来。问题是给定一个字符串，问是否能够通过重新排列组合一个合法的单词？这个问题不需要穷举所有情况，只需要找到一个合法单词即可，因而可用回溯算法加快效率。如果能够构成合法单词，我们return该单词；否则返回空串。问题的base case是检查字典中是否包含该单词。每次我们做出选择之后递归调用，判断做出当前选择之后能否成功，如果能，不再尝试其他可能；如果不能，我们换一个别的选择。代码如下：
?
复制代码
?1 string FindWord(string sofar, string rest, Dict& dict)
?2 {
?3 ? ? // Base Case
?4 ? ? if (sofar.empty())
?5 ? ? {
?6 ? ? ? ? return (dict.containWords(sofar)? sofar : "");
?7 ? ? }
?8?
?9 ? ? for (int i = 0; i < rest.size(); ++i)
10 ? ? {
11 ? ? ? ? // make a choice
12 ? ? ? ? string sofar2 = sofar + rest[i];
13 ? ? ? ? string rest2 = rest.substr(0, i) + rest.substr(i+1);
14 ? ? ? ? String found = FindWord(sofar2, rest2, dict);
15 ? ? ? ??
16 ? ? ? ? // if find answer
17 ? ? ? ? if (!found.empty()) return found;
18 ? ? ? ? // else continue next loop, make an alternative choice
19 ? ? }
20?
21 ? ? return "";
复制代码
?
?
我们可以对这个算法进行进一步剪枝来早些避免进入“死胡同”。例如，如果输入字符串是"zicquzcal"，一旦你发现了前缀"zc"你就没有必要再进行进一步的选择，因为字典中没有以“zc”开头的单词。具体说来，在base case中需要加入另一种终止条件，如果sofar不是有效前缀，直接返回“”。
?
【经典回溯问题1】八皇后问题
问题是要求在8x8的国际象棋盘上放8个queue，要求不冲突。（即任何两个queue不同行，不同列，不同对角线）。按照前面的基本范式，我们可以给出如下的伪代码及
C++代码：：
?
复制代码
#include
#include
using namespace std;
?
// Start in the leftmose column
//?
// If all queens are placed, return true
// else for (every possible choice among the rows in this column)
// ? ? ? ? ?if the queue can be placed safely there,
// ? ? ? ? ? ? make that choice and then recursively check if this choice lead a solution
// ? ? ? ? ?if successful, return true
// ? ? ? ? ?else, remove queue and try another choice in this colunm
// if all rows have been tried and nothing worked, return false to trigger backtracking
const int NUM_QUEUE = 4;
const int BOARD_SIZE = 4;
typedef vector > Grid;
?
void PlaceQueue(Grid& grid, int row, int col);
void RemoveQueue(Grid& grid, int row, int col);
bool IsSafe(Grid& grid, int row, int col);
bool NQueue(Grid& grid, int curcol);
void PrintSolution(const Grid& grid);
?
?
int main()
{
? ? vector > grid(BOARD_SIZE, vector(BOARD_SIZE, 0));
? ? if (NQueue(grid, 0))
? ? {
? ? ? ? cout << "Find Solution" << endl;
? ? ? ? PrintSolution(grid);
? ? }
? ? else
? ? {
? ? ? ? cout << "Cannot Find Solution" << endl;
? ? }
?
? ? return 0;
}
?
void PlaceQueue(Grid& grid, int row, int col)
{
? ? grid[row][col] = 1;
}
?
void RemoveQueue(Grid& grid, int row, int col)
{
? ? grid[row][col] = 0;
}
?
bool IsSafe(Grid& grid, int row, int col)
{
? ? int i = 0;
? ? int j = 0;
?
? ? // check row
? ? for (j = 0; j < BOARD_SIZE; ++j)
? ? {
? ? ? ? if (j != col && grid[row][j] == 1) return false; ? ?
? ? }
?
? ? // check col
? ? for (i = 0; i < BOARD_SIZE; ++i)
? ? {
? ? ? ? if (i != row && grid[i][col] == 1) retu