开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 算法合集：回溯 -> 正文阅读

[数据结构与算法]算法合集：回溯

说到回溯的算法题，就像是——好像会写但好像又不会写。回溯倒像是一种暴力枚举，另一种形式的dp递推——推不动回去不就是了嘛，搭配上剪枝或能比较快速的推动算法。

一、简单回溯——子集类回溯：选？不选？

诸如子集，全排列这种类型的题目就属于简单类型的回溯——只需要考虑当下是选还是不选
听上去挺抽象的，结合例题就很好理解

1、例题

1）例题一：LeetCode 77 组合
说白了从1 ~ n，选取k个数，返回所有组合
对一个链表，用递归进行维护，当长度小于k时表示还可以继续选数，当长度等于k时则返回

List<List<Integer>> ans;
List<Integer> set;
public List<List<Integer>> combine(int n, int k) {
    this.ans = new ArrayList<>();
    this.set = new ArrayList<>();
    getAns(k, 1);
    return ans;
}

private void getAns(int k, int index) {
    if (k == 0) {
        ans.add(new ArrayList<>(set));
        return;
    }
    // 选
    set.add(index);
    getAns(k - 1, index + 1);
    set.remove(set.size() - 1); // 还原
    // 不选
    getAns(k, index + 1);
}

两个关键点的理解点

利用递归体的栈空间，使得选完之后可以返回原先index的位置，以进行其他的处理
选完之后要还原来消除影响

这题还有一个关键的加速步骤——剪枝

若剩下所有的数都放进去了也占不满k个，则直接返回

private void getAns(int k, int n, int index) {
    if (k == 0) {
        ans.add(new ArrayList<>(set));
        return;
    }
    if (k > n - index + 1) // 剪枝
        return;
    // 选
	set.add(index);
	getAns(k - 1, n, index + 1);
	set.remove(set.size() - 1);
	// 不选
	getAns(k, n, index + 1);
}

2）例题二：LeetCode 46 全排列（数字无重复）
全排列需要讲所有数都要用上，所以此时不再是一直向后寻找待选择的对象，而是每次递归时都要寻找还没有使用过的数
下面提供基于位运算的解法，不了解位运算的可以参考我的另一篇博客：算法合集：位运算——就两个数字还想劝退我？
另外在注释中用boolean数组进行解释

int valid = 0; // boolean[] valid
List<List<Integer>> ans;
List<Integer> set;
public List<List<Integer>> permute(int[] nums) {
    this.ans = new ArrayList<>();
    this.set = new ArrayList<>();
    this.valid = (int)Math.pow(2, nums.length) - 1; // this.valid = new boolean[nums.length]
    getAns(nums, 0, nums.length);
    return ans;
}

private void getAns(int[] nums, int turn, int n) {
    if (turn == n) {
        ans.add(new ArrayList<>(set));
        return;
    }
    for (int i = 0; i < n; i++) // 每层递归都遍历一边来寻找未使用的数
        if (((valid >> i) & 1) == 1) { // if (valid[i] == false)，表示还没用过该数
            valid ^= 1 << i; // valid[i] = true
            set.add(nums[i]);
            getAns(nums, turn + 1, n);
            set.remove(set.size() - 1);
            valid ^= 1 << i; // valid[i] = false，还原
        }
}

3）例题三：LeetCode 47 全排列Ⅱ（数字可以重复）
与上一题不同的是，有重复的数字且不能返回相同的答案。若要加入“判定答案是否相同”的方法体无疑复杂度太大了。
可以考虑以下想法：

如果数组是有序的
那么当上一个数与当前的数相同时，就可以来判断是否会产生重复答案
产生重复答案的情况是：上一个数与当前的数相同，并且上一个数没有被选择时，若仍选择当前的数，就会产生重复

来证明一下：
考虑这个例子

[1, 1, 2]

我们以第一个1打头时
证明图1
当以红1打头时，红1已经被选择了，所以即使后面出现了蓝1，也可以直接选而不会重复
若以第二个1打头时
证明图2
当轮到蓝1打头时，如果红1没有被选，那么就不能去选红1，因为红1已经代表1作为开头过了，选择蓝1的话只会重复地又1开头

首先，对有序数组，当上一个数与当前的数相同时才会触发——产生相同答案的情况
当nums[i - 1] = nums[i] = x时，对于数x来说，当index = i - 1时，x第一次出现，并被答案数组收集
当index = i时，由于x在上一步已经出现过，并且已经作为答案被收集了，所以若nums[i - 1]没被选，再选则nums[i]会产生重复答案

下面提供基于位运算的解法，另外在注释中用boolean数组进行解释

List<List<Integer>> ans;
List<Integer> set;
int valid; // boolean[] valid
public List<List<Integer>> permuteUnique(int[] nums) {
    Arrays.sort(nums);
    this.ans = new ArrayList<>();
    this.set = new ArrayList<>();
    this.valid = (int)Math.pow(2, nums.length) - 1; // this.valid = new boolean[nums.length]
    getAns(nums, 0, nums.length);
    return ans;
}

private void getAns(int[] nums, int count, int n) {
    if (count == n) {
        ans.add(new ArrayList<>(set));
        return;
    }
    for (int i = 0; i < n; i++)
        if (((valid >> i) & 1) == 1) { // if (valid[i] == false)，还没使用过
        	/*
        	 * if (i > 0 && nums[i] == nums[i - 1] && valid[i - 1] == false)
        	 * 		continue;
        	 * 当前数与上一个数相同，并且上一个数未被使用，则跳过当前
        	 */
            if (i > 0 && nums[i] == nums[i - 1] && ((valid >> (i - 1)) & 1) == 1)
                continue;
            valid ^= 1 << i; // valid[i] = true
            set.add(nums[i]);
            getAns(nums, count + 1, n);
            set.remove(set.size() - 1); // 还原
            valid ^= 1 << i; // valid[i] = false
        }
}

2、实战题目

LeetCode 39 组合总数
 LeetCode 40 组合总数Ⅱ
LeetCode 216 组合总数Ⅲ
LeetCode 78 子集
 LeetCode 90 子集Ⅱ

二、复杂回溯——判断选择是否合法？

相比于简单回溯，复杂回溯仍是“选”与“不选”的问题，但多了一些处理与选择上的要求

1、例题

1）LeetCode 282 给表达式添加运算符
对于每次选择

不选：当前的数字不与前面的数字分隔开，也就是不添加运算符，直接进行下一次递归
选：先添加+，-，*等运算符，后添加当前数字，再进行进行递归

为了防止重复的操作，每次修改运算符时，不需要将运算符及其后的所以数字都删除，只需要直接找到运算符的位置修改即可：
以s = "123"举例，假设当前递归到i = 1，也就是数字2的位置
在这里插入图片描述
此时StringBuilder = "1"，也就是说，需要对当前的2进行处理

若不选，直接添加2后进行下一次递归
若选，则分别添加三个运算符

我们先插入一个'.'为运算符占位，并记录下这个'.'插入的位置，再添加数字
在这里插入图片描述
此时只需要修改.，变成+，-，*即可，而不用重复的删除添加数字了

builder.setCharAt(operIndex, '+');
builder.setCharAt(operIndex, '-');
builder.setCharAt(operIndex, '*');

接下来是递归参数的维护
维护一个long cur，cur表示当前已参与运算的式子的结果，再维护一个 long pre表示上一层的递归的数字，用于乘法的维护：
因为我们知道*的优先级高于-和+
所以当添加*时：
参数解释
乘法的函数体（i + 1，target和n可以先不看）

builder.setCharAt(operIndex, '*');
getAns(i + 1, pre * val, cur - pre + pre * val, target, n); // 进行下一次递归

pre * val：由于乘法的优先级最高，所以本次的val需要和上一层的pre形成一个整体传给下一层，作为下一层的pre
cur - pre + pre * val：由于乘法会使得上一层的pre和当前的val形成一个整体，所以cur的维护需要减去pre，再将pre * val作为整体进行添加

对比加减法的函数体来看

builder.setCharAt(operIndex, '+');
getAns(i + 1, val, cur + val, target, n);
builder.setCharAt(operIndex, '-');
getAns(i + 1, -val, cur - val, target, n);

最后是题解代码

List<String> ans;
StringBuilder builder;
char[] arr;
public List<String> addOperators(String num, int target) {
    this.ans = new ArrayList<>();
    this.builder = new StringBuilder();
    this.arr = num.toCharArray();
    getAns(0, 0L, 0L, target, num.length());
    return ans;
}

private void getAns(int index, long pre, long cur, int target, int n) {
    if (index == n) {
        if (cur == target)
            ans.add(builder.toString());
        return;
    }
    int operIndex = builder.length();
    if (index > 0)
        builder.append('.'); // 占位
    long val = 0;
    for (int i = index; i < n; i++) {
        val = val * 10 + (arr[i] - '0');
        // 直接添加数字，到后面再修改前面的oper
        builder.append(arr[i]);
        // 若index = 0，不能添加oper
        if (index == 0) {
            getAns(i + 1, val, val, target, n);
        } else {
            builder.setCharAt(operIndex, '+');
            getAns(i + 1, val, cur + val, target, n);
            builder.setCharAt(operIndex, '-');
            getAns(i + 1, -val, cur - val, target, n);
            builder.setCharAt(operIndex, '*');
            getAns(i + 1, pre * val, cur - pre + pre * val, target, n);
        }
        if (val == 0) // 排除连着的0的情况
            break;
    }
    builder.setLength(operIndex); // 还原
}

2）LeetCode 301 删除无效括号
我们知道有效的括号组合一定是count('(') = count(')')，即左右括号数量相等
所以可以先遍历字符串，找出哪种的括号多了，记录下需要删除的数量
比如：

s = "((())"，此时需要删除一个左括号

但有例外：

s = ")("，此时左右括号相等，但s是不合法的，需要删除左右括号各一个
s = ")(("，此时需要删除两个左括号和一个右括号

所以先计算至少需要删除的数量，再循环增加数量

this.arr = s.toCharArray();
int countL = 0, countR = 0; // 得到左右括号各自的数量
for (int i = 0; i < arr.length; i++) {
    if (arr[i] == '(') countL++;
    else if (arr[i] == ')') countR++;
}
// 得到左右括号需要删除的数量
int deleteL = Math.max(0, countL - countR), deleteR = Math.max(0, countR - countL);
// 循环增加需要删除的数量，进行递归
for (int i = 0; i <= Math.min(countL, countR); i++)
    getAns(0, deleteL + i, deleteR + i, 0, 0, true, new StringBuilder());

接下来是递归方法体的设计

getAns(int i, int deleteL, int deleteR, int countL, int countR, boolean pre, StringBuilder builder)

i对应s的下标，当i == s.length()时即可收集答案
deleteL和deleteR表示还需要删除的左右括号的数量
countL和countR表示递归到现在所遇到的左右括号的数量，均从0开始
pre表示上一个括号是否有被删除，用于剪枝

删：删除当前的括号。
也就是builder不添加此次的括号，并且deleteL和deleteR相应的减少
不删：不删除当前的括号
builder添加此次括号，deleteL和deleteR不变

// 删
if (arr[i] == '(' && (pre || arr[i - 1] != '(') && deleteL > 0)
    getAns(i + 1, deleteL - 1, deleteR, countL, countR, true, builder);
else if (arr[i] == ')' && (pre || arr[i - 1] != ')') && deleteR > 0)
    getAns(i + 1, deleteL, deleteR - 1, countL, countR, true, builder);
// 不删
builder.append(arr[i]);
if (arr[i] == '(')
    getAns(i + 1, deleteL, deleteR, countL + 1, countR, false, builder);
else if (arr[i] == ')')
    getAns(i + 1, deleteL, deleteR, countL, countR + 1, false, builder);
else    
    getAns(i + 1, deleteL, deleteR, countL, countR, false, builder);
builder.deleteCharAt(builder.length() - 1);

剪枝：

countR > countL，也就是当前遇到的右括号数量 > 左括号数量，直接返回
arr.length - i < deleteL + deleteR，还需要删除的括号数量 > 还没遍历到的括号数量，直接返回
去重，pre || arr[i - 1] != arr[i]，如果上一层的括号与本层的括号种类相同，并且上一层括号没有被删，则此时再删除当前括号会重复：比如s = "(()"，删除第一个左括号而不删第二个左括号，其效果与不删除第一个左括号但删除第二个左括号相同

List<String> ans;
char[] arr;
public List<String> removeInvalidParentheses(String s) {
    this.ans = new ArrayList<>();
    this.arr = s.toCharArray();
    int countL = 0, countR = 0;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == '(') countL++;
        else if (arr[i] == ')') countR++;
    }
    int deleteL = Math.max(0, countL - countR), deleteR = Math.max(0, countR - countL);
    for (int i = 0; i <= Math.min(countL, countR); i++) {
        getAns(0, deleteL + i, deleteR + i, 0, 0, true, new StringBuilder());
        // 如果当前的countL和countR找到了答案，则可以返回了
        // 如果没找到答案，则要增加countL和countR，如：s = ")(("
        if (ans.size() != 0) 
            break;
    }
    return ans;
}

private void getAns(int i, int deleteL, int deleteR, int countL, int countR, boolean pre, StringBuilder builder) {
    if (countR > countL || arr.length - i < deleteL + deleteR)
        return;
    if (i == arr.length) {
        ans.add(builder.toString());
        return;
    }
    // 删
    if (arr[i] == '(' && (pre || arr[i - 1] != '(') && deleteL > 0)
        getAns(i + 1, deleteL - 1, deleteR, countL, countR, true, builder);
    else if (arr[i] == ')' && (pre || arr[i - 1] != ')') && deleteR > 0)
        getAns(i + 1, deleteL, deleteR - 1, countL, countR, true, builder);
    // 不删
    builder.append(arr[i]);
    if (arr[i] == '(')
        getAns(i + 1, deleteL, deleteR, countL + 1, countR, false, builder);
    else if (arr[i] == ')')
        getAns(i + 1, deleteL, deleteR, countL, countR + 1, false, builder);
    else    
        getAns(i + 1, deleteL, deleteR, countL, countR, false, builder);
    builder.deleteCharAt(builder.length() - 1);
}