概念

回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

回溯法是一种选优搜索法，按选优条件向前搜索以达到目标。当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术称为回溯法，而满足回溯条件的某个状态的点称为回溯点。

许多复杂的、规模较大的问题都可以使用回溯法，有“通用解题方法”之称。

基本思想

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根节点出发深度优先搜索解空间树。当探索到某一结点时，要先判断节点是否包含问题的解，如果包含，就从该节点出发继续探索下去，如果不包含，则逐层向其祖先节点回溯。

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

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

步骤

针对所给问题，确定问题的解空间：首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。

确定结点的扩展搜索规则

以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索

子集树：当所给问题是从 n 个元素的集合 S 中找出 S 满足的某种性质的子集时，相应的解空间树称为子集树。例如，0-1背包问题，要求在n个物品的集合S中，选出几个物品，使物品在背包容积C的限制下，总价值最大（即集合S的满足条件 <容积C下价值最大> 的某个子集）。

子集树是从集合S中选出符合限定条件的子集，故每个集合元素只需判断是否（0,1）入选，因此解空间应是一颗满二叉树。

void backtrack(int t) { //t是当前层数
    if(t > n) output(x);
    else {
        for(int i = 0; i <= 1; i++) { //子集树是从集合S中，选出符合限定条件的子集，故每个元素判断是（1）否（0）选入即可（二叉树），因此i定义域为{0,1}
            x[t] = i; //x[]表示是否加入点集，1表示是，0表示否
            if(constraint(t) && bound(t)) //constraint(t)和bound(t)分别是约束条件和限定函数 
                backtrack(t + 1);
        }
    }
}

排列树：当问题是确定n个元素满足某种性质的排列时，相应的解空间称为排列树。排列树与子集树最大的区别在于，排列树的解包括整个集合S的元素，而子集树的解则只包括符合条件的集合S的子集。

void backtrack(int t) { //t是当前层数
    if(t > n) output(x);
    else {
        for(int i = t; i <= n; i++) {
            swap(x[t], x[i]);
            if(constraint(t) && bound(t))
                backtrack(t + 1);
            swap(x[i], x[t]);
        }
    }
}

非子集树，非排列数：

void backtrack(int t) {
    if(t > n) output(x);
    else {
        for(int i = f(n, t); i <= g(n, t); i++) {
            x[t] = h[i];
            if(constraint(t) && bound(t))
                backtrack(t + 1);
        }
    }
}

货箱装船问题

有两艘船，载重量为c1、c2，有n个货箱，重量分别为w1, w2, …, wn。

基本思路：容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。
(1)首先将第一艘轮船尽可能装满；
(2)将剩余的集装箱装上第二艘轮船。

将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近c1。由此可知，装载问题等价于特殊的0-1背包问题。

int n;       //货箱数目
int w[maxn]; //货箱重量数组
int c;       //第1艘船的载重量
int cw;      //当前装载的重量
int bestw;   //目前最优装载的重量

void maxLoading(int i) { //从第i层节点搜索
    if(i > n) {
        if(cw > bestw) bestw = cw;
        return;
    }
    if(cw + w[i] <= c) { //尝试x[i] = 1
        cw += w[i];
        maxLoading(i + 1);
        cw -= w[i]; //回溯
    }
    maxLoading(i + 1); //尝试x[i] = 0
}