算法概述
回溯法（Back Tracking Method）（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 “回溯点”。
可以把回溯法看成是递归调用的一种特殊形式。许多复杂的，规模较大的问题都可以使用回溯法，有 “通用解题方法” 的称号。
代码方面，回溯算法的框架：
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择(即:路径+1,并将此选择标记为不可选)
backtrack(路径, 选择列表)
撤销选择(即:路径-1,并将此选择标记为可选)
其核心是：for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。
回溯算法通常用于解决以下问题：
- 组合问题：例如八皇后问题，求出所有可能的组合。
- 排列问题：例如旅行商问题，求出所有可能的排列。
- 判断子集问题：例如填充背包问题，求出所有可能的子集。
三个例子
1. 电话按键的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如图所示（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
phone_keybord.jpg
分析:
这是一个全排列的问题, 结合上面伪代码的算法框架, 可以轻松完成排列
java代码示例:
public List<String> letterCombinations_backtrack(String digits){
List<String> result = new ArrayList<>();
backtrack(result, new StringBuffer(), digits, 0);
return result;
}
private void backtrack(List<String> result, StringBuffer eachResult, String digits, int level){
// 满足结束条件,添加路径到结果集并返回
if (level == digits.length()) {
result.add(eachResult.toString());
return;
}
List<String> levelChars = getChar(digits.charAt(level));
for (String levelChar : levelChars) {
// 做选择
eachResult.append(levelChar);
// 递归回溯
backtrack(result, eachResult, digits, level+1);
// 取消选择
eachResult.setLength(eachResult.length() -1);
}
}
public static List<String> getChar(char c) {
return switch (c) {
case '2' -> Arrays.asList("a", "b", "c");
case '3' -> Arrays.asList("d", "e", "f");
case '4' -> Arrays.asList("g", "h", "i");
case '5' -> Arrays.asList("j", "k", "l");
case '6' -> Arrays.asList("m", "n", "o");
case '7' -> Arrays.asList("p", "q", "r", "s");
case '8' -> Arrays.asList("t", "u", "v");
case '9' -> Arrays.asList("w", "x", "y", "z");
default -> new ArrayList<>();
};
}
扩展思考:
此问题可变种为, 给出一组元素, 求所有可能的排列, 例如输入[a, b, c], 返回[abc, acb, bac, bca, cab, cba]
2. 指定和为多少的组合
给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidate
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
示例 1：
输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
示例 4：
输入: candidates = [1], target = 1
输出: [[1]]
示例 5：
输入: candidates = [1], target = 2
输出: [[1,1]]
提示：
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500
分析:
注意所有元素都是可重复选取的, 如果target较大且备选元素中存在1时, 递归深度会比较大, 小心内存溢出
java代码示例:
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates.length <= 0) {
return result;
}
Arrays.sort(candidates);
// 记录「路径」
LinkedList<Integer> listRoute = new LinkedList<>();
backtrack(candidates, target, result, listRoute, candidates.length -1);
return result;
}
// 路径：记录在 track 中
// 选择列表：candidates 中不存在于 track 的那些元素
// 结束条件：candidates 中的元素全都在 track 中出现
private void backtrack(int[] candidates, int target, List<List<Integer>> result, LinkedList<Integer> listRoute, int start) {
// 触发结束条件
if (target == 0) {
result.add(new ArrayList<>(listRoute));
return;
}
for (int i = start; i >= 0; i--) {
// 排除不合法的选择
if (candidates[i] > target)
return;
// 做选择
listRoute.add(candidates[i]);
// 进入下一层决策树,目标值减少
backtrack(candidates, target-candidates[i], result, listRoute, i);
// 取消选择
listRoute.removeLast();
}
}
扩展思考:
此问题可变种为, 元素不能重复选取
3. N皇后问题
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击（皇后在横竖撇捺4个方向见面都会互相攻击）。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：[["Q"]]
提示：
1 <= n <= 9
N皇后.jpg
分析:
这道题主要是要考虑如何来表示四个约束条件：
1.每行只有一个
2.每列只有一个
3.每45°斜线只有一个
4.每135°斜线只有一个
约束条件可以考虑适用哈希表或者布尔数组来表示，我们选择使用布尔数组比较简单。
1.对于每行只有一个，我们可以在遍历的时候就以行为单元来遍历，即将每一行看成一个整体，比如N=4时，每一行就只有4种可能即["Q....",".Q..","..Q.","...Q"]，我们直接对这4种可能作遍历
2.对于每列只有一个，使用isColExist布尔数组来表示，长度为n, isColExist[i]表是第i列是否存在皇后
3.对于每45°角只有一个，需要懂点脑筋找规律了，以N=4为例，看下图：看相同的颜色，每一种颜色表示一条45°角斜线，这个比较明显，就是每一条45°斜线上的坐标(x,y)，x + y 都是相等的, 正好值也大于等于0, 因此可以直接映射到一维数组的索引上, 于是用is45DegreeExist布尔数组表示，长度为2*n-1
4.对于每135°角只有一个，和上面一样要找规律：看相同颜色，每一种颜色表示一条135°角斜线，映射的规律应该有多种，其中一种比较好找的是，每一条135°斜线上的坐标(x,y), y - x 都相等。因此同样使用is135DegreeExist布尔数组表示，长度为2*n-1, 因为值域为[-(n-1), n-1], 所以用(y-x) + (n-1)映射到一维数组的下标
其余就是回溯法的经典代码了
N皇后45°角.png
N皇后135°角.png
java代码示例:
public class NQueen_Solution {
private final LinkedList<String> eachRowAnswer; // 暂时存储符合条件的情况
private final List<List<String>> listAnswer; // 答案
NQueen_Solution(){
eachRowAnswer = new LinkedList<>();
listAnswer = new LinkedList<>();
};
private boolean[] isColExist; // 每一列是否已存在皇后
private boolean[] is45DegreeExist; // 正对角是否已存在皇后(45°)
private boolean[] is135DegreeExist; // 反对角是否已存在皇后(135°)
private char[] eachRowChar; // 每行的字符数组
private int queenSize; // N皇后的大小
public List<List<String>> solveNQueens(int n) {
// 初始化
isColExist = new boolean[n];
eachRowChar = new char[n];
Arrays.fill(eachRowChar,'.');
is45DegreeExist = new boolean[2*n-1];
is135DegreeExist = new boolean[2*n-1];
queenSize = n;
backtrack(0);
return listAnswer;
}
private void backtrack(int currentRowIndex){
if(currentRowIndex== queenSize){
listAnswer.add(new LinkedList<>(eachRowAnswer));
return;
}
// 这里循环的是每一行对应的列
for(int colIndex = 0; colIndex < queenSize; colIndex++){
// 45°角和135°角由二维数组转为一维数组是本算法的精华
int index45Degree = colIndex + currentRowIndex;
// 本来是colIndex-currentRowIndex,因为计算结果范围是从-(queenSize-1)到(queenSize-1), 这里直接加上(queenSize-1)映射到数组索引
int index135Degree = (colIndex - currentRowIndex) + (queenSize - 1);
if(!isColExist[colIndex] && !is45DegreeExist[index45Degree] && !is135DegreeExist[index135Degree]){
eachRowChar[colIndex] = 'Q';
eachRowAnswer.add(new String(eachRowChar));
eachRowChar[colIndex] = '.';
isColExist[colIndex] = true;
is45DegreeExist[index45Degree] = true;
is135DegreeExist[index135Degree] = true;
backtrack(currentRowIndex+1);
eachRowAnswer.removeLast();
isColExist[colIndex] = false;
is45DegreeExist[index45Degree] = false;
is135DegreeExist[index135Degree] = false;
}
}
}
}
扩展思考:
除了用一维数组存储45°角和135°角的占用情况, 有其他同样简洁优雅的方法吗?
网友评论