一、如何理解回溯算法
回溯的处理思想，有点类似枚举搜索。枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，把问题求解的过程分为多个阶段。每个阶段都会面对一个岔咯口，先随意选择一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。
二、回溯算法的经典应用
1、八皇后问题
有一个 8x8 的棋盘，希望往里放 8 个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子。
把这个问题分成8个阶段，依次钭8个棋子放到第一行、第二行......第八行。在放置的过程中不停的检查当前的方法，是否满足要求。如果满足，则跳到下一行继续放置棋子；如果不满足，那就再换一种方法，继续尝试。
回溯算法非常适合用递归来实现，代码实现如下：
// 存储皇后的位置，下标为行，值为列
int[] res = new int[8];
public void eightQueen(int row) {
// 已经完成
if (row == 8) {
// 打印已经放好的位置
printQueen();
return;
}
for (int col = 0; col < 8; col++) {
// 判断该列是否可以放置
if (isOk(row, col)) {
res[row] = col;
// 继续放下一行
eightQueen(row + 1);
}
}
}
// 判断是否符合要求放置棋子
private boolean isOk(int row, int col) {
for (int i = row - 1; i >= 0; i--) {
// 如果该列有棋子，不符合要求
if (res[i] == col) {
return false;
}
// 如果该位置对角线上有棋子，不符合要求;
// 两个位置的行,列相减的绝对值相等，说明是在同条对角线上
if (Math.abs(row - i) == Math.abs(col - res[i])) {
return false;
}
}
return true;
}
// 打印res数据,矩阵显示
private void printQueen() {
for (int row = 0; row < 8; row++) {
for (int col = 0; col < 8; col++) {
if (res[row] == col) {
System.out.print("Q ");
} else {
System.out.print("* ");
}
}
System.out.println();
}
System.out.println();
}
2、0-1 背包
有一个背包，背包总的承载重量是Wkg。现在有 n 个物品，每个物品的重量不等，并且不可分割。我们期望选择几个几件物品，装到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？
对于每个物品来说，都有两种选择，装进背包或者不装进背包。对于 n 个物品来说，总的装法就有 2^n 种。可以用回溯的方法来不重复的穷举这 2^n 种装法。先把品依次排列，整个问题就分解成了 n 个阶段，每个阶段对应一个物品怎么选择。代码实现如下：
// 背包所能承受物品总质量的最大值
int maxW = Integer.MIN_VALUE;
/**
* 装载背包
*
* @param i 要装载的物品下标
* @param cw 当前已经装载的重量
* @param items 物品数组
* @param n 物品的数量
* @param w 背包承载重量
*/
public void loadBag(int i, int cw, int[] items, int n, int w) {
if (cw == w || i == n) { // 装载的重量已经到达背包承受重量，或者物品已经装完了，可以退出
if (cw > maxW) { // 记录装载的重量
maxW = cw;
}
return;
}
// 不装当前物品
loadBag(i + 1, cw, items, n, w);
// 装当前物品，不过不能超过w
if (cw + items[i] <= w) {
loadBag(i + 1, cw + items[i], items, n, w);
}
}
3、正则表达式
正则表达式里最重要的一种算法思想就是回溯。
正则表达式中，最重要的就是通配符，通配符结合在一起，可以表达非常丰富的语义。 我们现在假设正则表达式中保包含 “ * ” 和 “ ? ” 这两种通配符，并且对这两个通配符的语义稍微做些改变，“ * ” 匹配任意多个（大于等于0个）任意字符，“ ? ” 匹配零个或者一个任意字符。基于以上背景假设，判断一个给定的文本，能否跟给定的正则表达式匹配？
我们依次考察正则表达式中的每个字符，当是非通配符时，直接跟文本的字符进行匹配，如果相同，则继续往下处理；如果不同，则回溯； 当遇到特殊字符时，有多种处理方式，也就是所谓的岔路吕，比如 “ * ”，有多种匹配方案，可以匹配任意个文本串中的字符，我们就先阴间的选择一种匹配方案，然后继续考察剩下的字符。如果中途发现无法继续匹配下去了，我们就回到这个岔路吕，重新选择一种匹配方案，再继续匹配剩下的字符。代码实现如下
/**
* 正则表达式
*
* @Author YBF
* @Date 2023/5/17
*/
public class Pattern {
// 正则表达式
private char[] pattern;
// 正则表达式长度
private int plen;
// 匹配标识
private boolean matched = false;
public Pattern(char[] pattern, int plen) {
this.pattern = pattern;
this.plen = plen;
}
/**
* 匹配字符串
* @param text 文本
* @param tlen 文本长度
* @return 是否匹配
*/
public boolean match(char[] text, int tlen) {
matched = false;
rmatch(0, 0, text, tlen);
return matched;
}
/**
* 正则表达式匹配
*
* @param ti 文本下标
* @param pj 正则表达式下标
* @param text 文本
* @param tlen 文本长度
*/
private void rmatch(int ti, int pj, char[] text, int tlen) {
// 如果已经匹配了，就不用继续下去了
if (matched) return;
// 正则表达式到结尾了
if (pj == plen) {
// 文本也到结尾了,匹配上了
if (ti == tlen) {
matched = true;
}
return;
}
// 如果正则表达式当前字符是*
if (pattern[pj] == '*') {
// 匹配比较文本字符与下一个正现表达式下一个字符
for (int i = ti; i < tlen; i++) {
rmatch(i, pj + 1, text, tlen);
}
} else if (pattern[pj] == '?') { // 如果正则表达式当前字符是 ？
// 匹配 0 个字符
rmatch(ti, pj + 1, text, tlen);
// 匹配 1 个字符
rmatch(ti + 1, pj + 1, text, tlen);
} else if (ti < tlen && text[ti] == pattern[pj]) { // 正则表达式是普通字符，与文本字符相同往下继续匹配
rmatch(ti + 1, pj + 1, text, tlen);
}
}
}
