最近几天在leetcode上刷到排列组合这一类的问题多了起来.
.基本的解决思路就是“回溯算法”，乍一看感觉非常高大上，其实也就是披着多叉树遍历外套的暴力破解法，做多了就会发现这就像循环遍历数组一样，套路固定，故准备总结在此，以供交流探讨。
2020年9月15日10:04:30
第4次更次博客，今天的leetcode题目是解数独，用回溯法解的非常漂亮，忍不住想分享出来。
2020年9月18日09:42:44
第5次更新，今天的leetcode题目虽然是求排列组合的全排列，但是涉及到去重，还有一个涉及到去重的问题是，基本思路都是先进行排序，然后再做一系列操作。
1 模板
举个例子：输出一串数字[1,2,3]的全排列[1,2,3]，[1,3,2]，[2,1,3]，[2,3,1]，[3,1,2]，[3,2,1]。
这个问题交给人类来解决的话肯定是先固定第一位为 1，然后第二位可以是 2，那么第三位只能是 3；然后可以把第二位变成 3，第三位就只能是 2 了；然后就只能变化第一位，变成 2，然后再穷举后两位，以此类推......
就像下面这样的一个树形结构：
当我们停留在每一个 节点上时，都需要做一个决策，例如停留在图中红色节点上时，有[1, 3]两个数字可以做选择，如果选择了1之后再选择数字3（最后一个数字只有一个选项），则已经找到了一个不重复的数字，这一次的选择就结束了，我们会退回红色的节点继续向右子树搜索，以此类推......直到找到左右的结果。
这其实就是回溯算法，中学的时候就已经不自觉地掌握了。我们可以抽象一点，把整个算法的解决模板给概括出来，即：
解决一个回溯问题，实际上就是一个决策树的遍历过程，确定了以下三个条件，问题就迎刃而解了：
- 路径：已经做出的选择
- 选择列表：当前可以做的选择
- 结束条件（递归出口）：到达决策的底层，没有选择可做的条件
伪代码如下：
List<T> result = new ArrayList<>();
private void backtrack(路径, 选择列表){
if(满足结束条件){
result.add(路径);
return;
}
for(选择 : 选择列表){
做选择;
backtrack(路径, 选择列表);
撤销选择;
}
}
上面蓝色文字“决策”对应的就是代码中的“做选择”，“结束”对应“满足结束条件”，“退回”对应“撤销选择”
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。
多说无益，上例子。
2 排列组合问题
2.1 leetcode 77 组合
评论区里面的图画的已经非常直观了，我这里直接引用一下
根据我上面给的三个条件，将其对应在本题中如下：
- 路径：就是图中红色方块部分，当然树干上面“取X”也是路径
- 选择列表：就是图中蓝色方块部分
- 结束条件：路径中包含k个数字时。
我们定义的函数其实就像是一个指针，将这棵树的所有节点都走一遍之后整个程序就执行完毕了，所得的结果就是正确结果。如何将这棵树所有的节点都走一遍？其实就是前序遍历，中序遍历，后序遍历：
private traverse(TreeNode root){
for(TreeNode child : root.children){
traverse(child);
}
}
我们做选择以及撤销选择的动作正是在前序和后序的时间点做出的，即做了一个选择之后到下一个节点，将做的选择撤销以后回到上一个节点！
所以回溯算法的核心框架：
for(选择 : 选择列表){
// 做选择
将被选的项从候选表中删除;
路径.add(选择);
backtrack(路径, 选择列表);
// 撤销选择
路径.remove(选择);
重新将被选的项加入候选表;
}
我们只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到每个节点的选择列表和路径。
本题解决方案如下：
class Solution {
private List<List<Integer>> result = new ArrayList<>();
// 用一个栈来记录每一个组合
private void findCombinations(int n, int k, int begin, Stack<Integer> pre){
if(pre.size() == k){
result.add(new ArrayList<>(pre));
return;
}
for(int i = begin; i <= n; i ++){
pre.push(i);
findCombinations(n, k, i + 1, pre); // 从下一个数字开始取
// 当前数字的情况已经全部取完，弹出栈顶元素
pre.pop();
}
}
public List<List<Integer>> combine(int n, int k) {
if (n <= 0 || k <= 0 || n < k) {
return result;
}
findCombinations(n, k, 1, new Stack<>());
return result;
}
}
这一部分就是递归出口（可以结合题意理解，我们只要找到k个数字就好）
每一个数字 i 就是要做的选择
返回用一个List来存储（当然其他的数据结构都可以~）
撤销选择操作，其实就是做选择的逆动作
2.2 leetcode 216 组合总和III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
这种找出总和为某数字的问题，套路也很固定，只需在回溯函数里多添加一个遍历target用于记录求和的目标是多少即可。
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> temp = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
dfs(k, n, 1);
return result;
}
private void dfs(int k, int sum, int start){
if(k == 0 && sum == 0){ // 符合条件
result.add(new ArrayList<>(temp)); // 注意深拷贝和浅拷贝！！必须是new一个新数组
return;
}
if(k == 0 || sum < 0) return; // 不符合条件
for(int i = start; i <= 9; i ++){
temp.add(i);
dfs(k - 1, sum - i, i + 1);
temp.remove(temp.size() - 1); // 回溯
}
return;
}
}
2.3 leetcode 60 组合总和III
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。
leetcode上面的一个题解很优秀，这里引用一下。
public String getPermutation(int n, int k) {
int[] nums = new int[n];//生成nums数组
for (int i = 0; i < n; i++){
nums[i] = i + 1;
}
boolean[] used = new boolean[n];//记录当前的索引的数是否被使用过
return dfs(nums, new ArrayList<String>(), used, 0, n, k);
}
/**
* @param nums 源数组
* @param levelList 每一层的选择
* @param used 数组的元素是否被使用过
* @param depth 深度，也就是当前使用的元素的索引
* @param n 上限值
* @param k 第k个
* @return 第k个排列
*/
private String dfs(int[] nums, List<String> levelList, boolean[] used, int depth, int n, int k) {
if (depth == n) {//触发出口条件，开始收集结果集
StringBuilder res = new StringBuilder();
for (String s : levelList){
res.append(s);
}
return res.toString();
}
int cur = factorial(n - depth - 1);//当前的depth也就是索引，有多少排列数
for (int i = 0; i < n; i++) {
if (used[i]) continue;//当前元素被使用过，做剪枝
if (cur < k) {//当前的排列组合数小于k，说明就算这一层排完了，也到不了第k个，剪枝
k -= cur;
continue;
}
levelList.add(nums[i] + "");//list收的是string类型
used[i] = true;//当前元素被使用过标记
return dfs(nums, levelList, used, depth + 1, n, k);
}
return null;
}
//返回n的阶乘，如3!=3*2*1=6
private int factorial(int n) {
int res = 1;
while (n > 0) {
res *= n--;
}
return res;
}
2.4 全排列II
给定一个可包含重复数字的序列，返回所有不重复的全排列。
涉及到去重的问题，一般思路都是将候选数组进行排序，然后再做一系列操作。这里我们选择对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」，即如下的判断条件：
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
详细代码如下：
class Solution {
private boolean[] used;
private List<List<Integer>> result;
public List<List<Integer>> permuteUnique(int[] nums) {
used = new boolean[nums.length];
result = new ArrayList<>();
Arrays.sort(nums);
backtrack(nums, new ArrayList<>(), 0);
return result;
}
private void backtrack(int[] nums, List<Integer> path, int index){
if(index >= nums.length){
result.add(new ArrayList<Integer>(path));
return;
}
for(int i = 0; i < nums.length; i ++){
if(used[i]){
continue;
}
// 只使用重复数字的第一个
// !used[i - 1] 说明当前重复数字左边还有未使用过的
if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
continue;
}
path.add(nums[i]);
used[i] = true;
backtrack(nums, path, index + 1);
// 回溯
used[i] = false;
path.remove(path.size() - 1);
}
}
}
3 子序列问题
当然排列组合问题当然不仅限于全排列问题，还有可能让我们从候选项中选出一些元素出来，就是所谓的求子序列。
leetcode 1079 活字印刷
你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
注意：本题中，每个活字字模只能使用一次。
示例 1：
输入："AAB"
输出：8
解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。
同样是明确三个条件：
- 路径：同上题，先前已经选择的字母组成的字符串。
- 选择列表：剩下可供选择的字母，即 title 中除了被用掉的字母之外的所有字母
- 结束条件：由于每一个结果的长度不是固定的，而且我们只需要统计个数，所以在生成"AA"的途中我们必然会经过"A"，这是计数器也要进行累加。
这个题目算是比较特殊的，只用统计最后子序列的个数，所以在递归调用时不需要再传入路径和选择列表，不过在分析问题的时候还是要明确这两个概念，这样才不至于代码出错。
参考代码：
class Solution {
int result = 0;
public int numTilePossibilities(String tiles) {
char[] counter = new char[26];
for(int i = 0; i < tiles.length(); i ++){
counter[tiles.charAt(i) - 'A'] ++;
}
backtrack(counter);
return result;
}
private void backtrack(char[] counter){
for(int i = 0; i < 26; i ++){
// 剪枝，即排除无效选择
if(counter[i] == 0) continue;
// 进行一次具体选择，本题就是 i 计数器减 1
counter[i] --;
// 一次有效枚举，总的计数器加 1
result ++;
// 继续回溯：递归 + 选择（尽可能剪枝） + 回退之前的现场恢复
backtrack(counter);
// 回退之前，也就是进入另一分支之前，恢复当前分支的改动
counter[i] ++;
}
}
}
由于并不需要输出最后得结果，所以只用将每个字母出现的频率统计出来就好（所幸英文字母的数量是可数的）。
一个选择就是选了一个字母，相应的频率减一就ok。
撤销选择就是将刚刚选择的字母重新放回候选列表中，即相应的字母频率加一。
4 子序列问题2
上面的问题其实是讨巧的，英文单词个数只有26个，并且只用输出序列的个数就可以了。如果将字母换做数字，那么就还是要老老实实地按照回溯的流程去做。
leetcode 面试题 08.04 幂集
幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。
说明：解集不能包含重复的子集。
分析的三个条件和上题类似，只不过是将字母变作数字。
由于是子序列，所以我们在从 0 到 length - 1 遍历候选数组时有一些数字是可以不选的，因此就会在递归调用时产生分叉，只需多考虑一种情况即可。
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
dfs(nums, 0);
return result;
}
private void dfs(int[] nums, int index){
if(index >= nums.length){
result.add(new ArrayList<>(temp)); // 注意浅拷贝
return;
}
// 不选择当前数字
dfs(nums, index + 1);
// 选择当前数字
temp.add(nums[index]);
dfs(nums, index + 1);
// 回溯
temp.remove(temp.size() - 1);
}
}
当遍历数组的索引值超出数组范围时就是返回条件：
有两种情况需要考虑：选择当前数字 / 不选当前数字 ：
如果选择了当前数字的话就需要在结果集temp中进行添加
撤销选择操作就是将刚刚选择的数字从路径中删除即可：
5 24点游戏
leetcode 679 24点游戏
一共有 4 个数和 3 个运算操作，因此可能性非常有限。一共有多少种可能性呢？
首先从 4 个数字中有序地选出 2 个数字，共有 4×3=12 种选法，并选择加、减、乘、除 4 种运算操作之一，用得到的结果取代选出的 2 个数字，剩下 3 个数字。
实现时，有一些细节需要注意。
- 除法运算为实数除法，因此结果为浮点数，列表中存储的数字也都是浮点数。在判断结果是否等于 24 时应考虑精度误差，这道题中，误差小于 10^{-6}可以认为是相等。
- 进行除法运算时，除数不能为 0，如果遇到除数为 0 的情况，则这种可能性可以直接排除。由于列表中存储的数字是浮点数，因此判断除数是否为 0 时应考虑精度误差，这道题中，当一个数字的绝对值小于 10^{-6}时，可以认为该数字等于 0。
一共有 4 个数和 3 个运算操作，因此可能性非常有限。
首先从 4 个数字中有序地选出 2 个数字，共有 4×3=12 种选法，并选择加、减、乘、除 4 种运算操作之一，用得到的结果取代选出的 2 个数字，剩下 3 个数字。
实现时，有一些细节需要注意。
- 除法运算为实数除法，因此结果为浮点数，列表中存储的数字也都是浮点数。在判断结果是否等于 24 时应考虑精度误差，这道题中，误差小于 10^{-6}可以认为是相等。
- 进行除法运算时，除数不能为 0，如果遇到除数为 0 的情况，则这种可能性可以直接排除。由于列表中存储的数字是浮点数，因此判断除数是否为 0 时应考虑精度误差，这道题中，当一个数字的绝对值小于 10^{-6}时，可以认为该数字等于 0。
class Solution {
static final int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;
public boolean judgePoint24(int[] nums) {
List<Double> list = new ArrayList<Double>();
for (int num : nums) {
list.add((double) num);
}
return backtrack(list);
}
public boolean backtrack(List<Double> list) {
if (list.size() == 0) {
return false;
}
if (list.size() == 1) {
return Math.abs(list.get(0) - 24) < 1e-6;
}
int size = list.size();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i != j) { // 选出来i，j这两个位置的数字做四则运算
List<Double> list2 = new ArrayList<Double>();
for (int k = 0; k < size; k++) {
if (k != i && k != j) { // 剩下的数字保持不变
list2.add(list.get(k));
}
}
for (int k = 0; k < 4; k++) {
if (k == ADD) { // 加法
list2.add(list.get(i) + list.get(j));
} else if (k == MULTIPLY) { // 乘法
list2.add(list.get(i) * list.get(j));
} else if (k == SUBTRACT) { // 减法
list2.add(list.get(i) - list.get(j));
} else if (k == DIVIDE) { // 除法
if (Math.abs(list.get(j)) < 1e-6) { // 分母不能为0
continue;
} else {
list2.add(list.get(i) / list.get(j));
}
}
if (backtrack(list2)) {
return true;
}
// 回溯
list2.remove(list2.size() - 1);
}
}
}
}
return false;
}
}
6 N皇后问题（放置问题）
决策树的每一层表示棋盘的每一行，每个节点可以做的选择是在该行任意位置放置一个皇后。
路径：board，其中小于row的那些行都已经选好了放皇后的位置
选择列表：第row行的每一个位置
返回条件：row超出borad范围
class Solution {
private List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
List<String> board = new ArrayList<>();
for(int i = 0; i < n; i ++){
String temp = "";
for(int j = 0; j < n ; j ++){
temp += '.';
}
board.add(temp);
}
backtrack(board, 0);
return res;
}
// 路径：board，其中小于row的那些行都已经选好了放皇后的位置
// 选择列表：第row行的每一个位置
// 返回条件：row超出borad范围
private void backtrack(List<String> board, int row){
if(row == board.size()){
res.add(new ArrayList<>(board));
return;
}
int n = board.get(row).length();
for(int col = 0; col < n; col ++){
if(!valid(board, row, col)){
continue;
}
char[] str = board.get(row).toCharArray();
// 做选择
str[col] = 'Q';
board.set(row, new String(str));
// 回溯
backtrack(board, row + 1);
// 撤销选择
str[col] = '.';
board.set(row, new String(str));
}
}
// 是否可以在该位置放置
private boolean valid(List<String> board, int row, int col){
int n = board.get(row).length();
// 检查列
for(int i = 0; i < n; i ++){
if(board.get(i).charAt(col) == 'Q'){
return false;
}
}
// 检查右上方
for(int i = row - 1, j = col + 1; i >= 0 && j < n; i --, j ++){
if(board.get(i).charAt(j) == 'Q'){
return false;
}
}
// 检查左上方
for(int i = row - 1, j = col - 1; i >=0 && j >= 0; i --, j --){
if(board.get(i).charAt(j) == 'Q'){
return false;
}
}
return true;
}
}
7 搜索所有可行解
7.1 leetcode 39 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
定义递归函数 backtrack(int[] candidates, int target, List<Integer> path, int startIndex) 表示当前在 candidates 数组的第 startIndex 位，还剩 target 要组合，已经组合的列表为 path。
递归的终止条件为 target <= 0 或者 candidates 数组被全部用完。那么在当前的函数中，每次我们可以选择跳过不用第 startIndex 个数，即执行 backtrack(candidates, target, path, startIndex + 1)。也可以选择使用第 startIndex个数，即执行 dfs(candidates, target - candidates[startIndex ], combine, startIndex ).
注意到每个数字可以被无限制重复选取，因此搜索的下标仍为 startIndex 。
class Solution {
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<Integer> path = new ArrayList<>();
backtrack(candidates, target, path, 0);
return result;
}
private void backtrack(int[] candidates, int target, List<Integer> path, int startIndex){
if(startIndex == candidates.length){
return;
}
if(target == 0){
result.add(new ArrayList<Integer>(path));
return;
}
// 不选当前数字
backtrack(candidates, target, path, startIndex + 1);
// 选当前数字
if(target >= candidates[startIndex]){
path.add(candidates[startIndex]);
// 每个数字可以被无限制重复选取，因此搜索的下标仍为 startIndex
backtrack(candidates, target - candidates[startIndex], path, startIndex);
// 回溯
path.remove(path.size() - 1);
}
}
}
7.2 组合总和II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
和上面的题目框架是类似的，只不过上题要求数字可以无限次使用，本题要求数字只能被用一次，所以需要去重操作，一个简单的去重思路是将数组进行从小到大排序，当后面一个数字等于前面一个数字时直接continue。其余框架不变。
class Solution {
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<Integer> path = new ArrayList<>();
Arrays.sort(candidates);
backtrack(candidates, target, path, 0);
return result;
}
private void backtrack(int[] candidates, int target, List<Integer> path, int startIndex){
if(target == 0){
result.add(new ArrayList<Integer>(path));
return;
}
for(int i = startIndex; i < candidates.length; i ++){
if(candidates[i] > target){
break;
}
// 保证不重复
if(i > startIndex && candidates[i] == candidates[i-1]){
continue;
}
path.add(candidates[i]);
backtrack(candidates, target - candidates[i], path, i + 1);
path.remove(path.size() - 1);
}
}
}
8 回溯和图的遍历结合
leetcode 79 单次搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
设函数check(i,j,k) 判断以网格的 (i, j) 位置出发，能否搜索到单词 word[k..]
路径：当前匹配到的位置k
返回条件：k移动到word尾或者i，j超出二维数组边界
class Solution {
public boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; ++i) {
for (int j = 0; j < board[i].length; ++j) {
if (board[i][j] == word.charAt(0)) {
if (backtrack(board, word, i, j, 0)) return true;
}
}
}
return false;
}
private boolean backtrack(char[][] board, String word, int i, int j, int k){
if (k == word.length()) {
return true;
}
if (i < 0 || j < 0 || i >= board.length || j >= board[i].length) {
return false;
}
if (word.charAt(k) != board[i][j]) {
return false;
}
// 匹配当前位置
char t = board[i][j];
board[i][j] = '0';
boolean res = backtrack(board, word, i + 1, j, k + 1) ||
backtrack(board, word, i - 1, j, k + 1) ||
backtrack(board, word, i, j + 1, k + 1) ||
backtrack(board, word, i, j - 1, k + 1);
// 回溯
board[i][j] = t;
return res;
}
}
9 求解数独
求解数独的思路就是对每一个格子所有可能的数字1-9进行穷举，基于此，我们可以写出代码框架：
public void solveSudoku(char[][] board) {
backtrack(board, 0, 0);
}
// 从左上角(r,c)开始回溯求解数组
public void backtrack(char[][] board, int r, int c){
int m = 9;
int n = 9;
// 对棋盘的每个位置进行穷举
for (int i = r; i < m; i++) {
for (int j = c; j < n; j++) {
for (char ch = '1'; ch <= '9'; ch ++) {
// 做选择
board[i][j] = ch;
// 继续穷举下一个
backtrack(board, i, j + 1);
// 撤销选择
board[i][j] = '.';
}
}
}
}
如果 j 到最后一列了我们应该从下一行开始继续，如果 i 到最后一行了我们就等于穷举完了所有情况，返回即可。为了减少复杂度，我们可以让backtrack函数返回值为boolean，如果找到一个可行解就返回 true，这样就可以阻止后续的递归。
class Solution {
public void solveSudoku(char[][] board) {
backtrack(board, 0, 0);
}
// 从左上角(r,c)开始回溯求解数组
public boolean backtrack(char[][] board, int r, int c){
int m = 9;
int n = 9;
if(c == n){
// 到最后一列则从下一行开始
return backtrack(board, r + 1, 0);
}
if(r == m){
return true;
}
// 对每个位置穷举
for(int i = r; i < m; i ++){
for(int j = c; j < n; j ++){
// 此处已经有数字
if(board[i][j] != '.'){
return backtrack(board, i , j + 1);
}
for(char ch = '1'; ch <= '9'; ch ++){
if(!isValid(board, i, j, ch)){
continue;
}
board[i][j] = ch;
if(backtrack(board, i, j + 1)){
return true;
}
board[i][j] = '.';
}
// 穷举完仍没找到
return false;
}
}
return false;
}
public boolean isValid(char[][] board, int r, int c, char ch){
for(int i = 0; i < 9; i ++){
// 判断行是否有重复数字
if(board[r][i] == ch){
return false;
}
// 判断列是否有重复数字
if(board[i][c] == ch){
return false;
}
// 判断3×3区域内是否有重复数字
if(board[(r/3)*3 + i/3][(c/3)*3 + i%3] == ch){
return false;
}
}
return true;
}
}
10 总结
回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作。
写回溯函数时，需要维护走过的路径和当前可以做的选择列表，当满足结束条件时，将路径记入结果集。
