当前位置：首页 > news >正文

【递归，搜索与回溯算法综合练习】深入理解暴搜决策树：递归，搜索与回溯算法综合小专题（一）

news 2025/7/9 3:02:50

找出所有子集的异或总和再求和

题目解析

算法原理

解法

决策树

这种决策使得每一次递归都是有效的递归，每一个节点都是最终的结果，所以这棵决策树是不用剪枝的，也没有递归出口的；

注意

决策树执行添加元素的操作前，要先从子集末尾元素在 nums 的位置后面是否还有元素，如果有元素则可以添加，反之，则不可以添加；

全局变量

开始时，子集是空集，所以异或的结果为 0 ，path 初始值刚好是0，所以不用处理子集为空的情况；

函数结构

在递归到决策树的某一层时，要知道从 nums 的哪个元素开始向后枚举，因此设计 dfs(nums,pos)

编写代码

虽然没有写 return 来回溯，但是在每次向下递归新一层的 dfs 时，这层 dfs 执行完，就会自动返回上一层的 dfs；

全排列Ⅱ

题目解析

算法原理

这道题其实就是全排列Ⅰ的plus 版本，只是多了重复的数，大体框架和全排列Ⅰ相同，只是剪枝操作需要更细致一点，全排列Ⅰ的解法可以先看下面这篇博客的第一题：

【递归，搜索与回溯算法】穷举 vs 暴搜 vs 深搜 vs 回溯 vs 剪枝算法入门专题详解

两道题唯一的出入的就是剪枝操作，所以我们下面只讲全排列Ⅱ该如何剪枝；

1. 两种剪枝

1. 在同一个节点（如图中的黑色节点）的所有分支中，相同的元素只能选择一次：

2. 同一个数只能使用一次，可以设置一个 check[] 数组来标记一下用过的数为 true

1.1 根据两种剪枝完善决策树

2. 两种思考方式

本质相同，都是针对是否需要剪枝的情况作出相应的处理；

3. 只关心不合法的分支（被剪枝的分支）

红色剪枝条件 check[ i ] == true，表示同一个数只能使用一次

粉色剪枝条件 nums[ i ] == nums [ i -1 ]，表示同一个节点的所有分支中，相同数只能使用一次

3.1 问题一：如果 nums 中重复元素不是连在一起的，那么这个判断条件无法使用

3.1.1 问题解析

如果我们要全排列的数组是 [ 1 , 2 , 1 , 3 , 1 ]，那么无法判断同一个节点，其中一条分支要递归的数，是否在前面分支中已经出现过了；

3.1.2 解决办法

我们可以在正式递归之前，先对 nums 数组先进行排序，方便后续的剪枝操作；在大多数情况下，排序数组的时间复杂度O(N*logN)，对于递归O(2^N)来说可以忽略不记；

3.2 问题二：无法筛查掉红色剪枝的分支，和合法分支相邻的情况

3.2.1 问题解析

nums[ i ] == nums [ i -1 ] 这个对不合法分支的判断条件范围还是太广了，无法筛查掉红色剪枝的分支，和合法分支（不应该被剪枝的分支）相邻的情况；

因为这些分支所代表的数是相同的，所以 nums[ i ] 所在的分支会被识别为不合法分支，而被执行粉色剪枝；

但是实际上，被红色剪枝的 nums[ i -1 ] 所在分支，本身就是不合法分支；

只有当 nums[i-1]和 nums[i] 两条分支都是合法的时候，才需要判断 nums[ i ] 是否等于 nums[ i - 1 ]

3.2.2 解决办法

我们要把下面这两种情况区分开：

那么怎么区分开呢？其实非常简单；就是判断两个数是否在决策树的同一层；

(1) 对于不同层：

两个数不是同一层，哪怕 nums[ i ] == nums [ i - 1 ]，nums[ i -1 ] 所在分支肯定也会被执行红色剪枝，因此 nums[i] 所在分支就是合法分支；

(2) 对于同一层：

如果递归时发现check[i-1]==false，则说明 nums[i-1] 和 nums[i] 所在位置为决策树同一层，如果是同一层，并且这两个数还相等，此时递归 nums[i] 的分支就是不合法的分支；

(3) 改进条件

我们在准备对 nums [ i ] 进行递归时，先判断 check[i] == false，如果 check[ i -1 ] == false ，那么就可以判断 nums[i-1] 和 nums[i] 在同一层；

对同一层进行进一步判断，如果 nums[i-1] == nums[i]，说明 nums[i] 所在分支不合法；

3.3 问题三：i = 0时，访问 nums[ i -1 ] 会越界

只关心不合法分支的最终判断条件： i != 0 && check[ i ] == false && num[i]==nums[i-1]

3.4 总结不合法分支

4. 只关心合法的分支（不被剪枝的分支）

4.1 先判断该节点是否已经被使用（是否会被执行红色剪枝）

如果我们的思考链路是只关心分支合法，那么第一步就是检查该分支是否被红色剪枝：

所以第一步就是判断 check [ i ] == false；

合法分支是一条不被执行红色剪枝 && 不被执行粉色剪枝的分支，所以在判断该分支不被执行红色剪枝后，我们就需判断该分支是否被执行粉色剪枝；

4.2 节点未被使用的情况下，是否被执行粉色剪枝

4.2.1 节点在决策树的深度相同，但是代表的数不同

我们先来分析下面这条分支，在检查完 check[ i ] == false 而不被执行红色剪枝之后之后，我们来判断是否被粉色剪枝：

显然，nums[ i ] != nums[ i -1 ]，因此肯定不会执行粉色剪枝（nums 已经提取排好序了）；

此时的判断条件为 check[ i ] ==false && ( nums [ i ] ! = nums [ i-1] .......)

4.2.2 节点代表的数相同，但是该节点前一条分支已经被使用

如果 nums[ i ] == nums [ i - 1 ]，但是 nums[ i - 1 ] 已经被使用过了，此时 check [ i - 1 ] == true，那么此时的分支也是合法的；所以此时的判断条件：

4.2.3 当 i = 0 的情况

如果只是考虑当前分支是否合法，那么 i 是可以等于 0 的；

i = 0 表示的是数组第一个元素，只要确保 check[ 0 ] ==false，就一定是可以大胆枚举的；因为这是对 nums 的第一个元素进行枚举的分支，这条分支必定是合法分支（一定是从考虑合法分支的角度出发）；

此时的判断条件：

5. 两种思考方式判断条件的区别

如果考虑当前分支不合法，就需要根据前一条分支的具体情况，来对当前分支的合法与否作出判断，如果当前分支的 i=0，则会出现数组越界；

6. 处理细节问题

7. 编写代码

7.1 只关心不合法分支

7.2 只关心合法分支

电话号码的字母组合

题目解析

算法原理

解法一 : 暴力枚举

定义两层 for 循环，对字符映射的数字的所有组合进行暴力枚举；但是如果一个字符映射的数字过多，使用暴力枚举是不好操作的；

解法二：深度优先遍历

决策树

对决策树进行一次深度优先遍历，在叶子节点收集结果即可；

解决数字和字符串的映射关系

我们可以使用字符串数组，让字符串数组前两个位置空着，让下标为2的数组元素存 "abc" 这个字符串，往后依此类推；

我们在遍历原始字符串的时候，拿到字符'2'之后，减去字符' 0 '对应的 Ascii 码值，就可以对应字符串数组的下标元素；

全局变量

设计函数

编写代码

括号生成

题目解析

算法原理

给一个括号子串，必须从头到尾遍历子串的每一个括号字符，如果在遍历的过程中，出现左括号的数量大于右括号的数量，那么这个子串就一定不是有效括号子串：

解法：暴搜

决策树

蓝色剪枝表示添加 ( 数量大于 n 剪枝；
紫色剪枝表示添加 ) 数量大于 ( 的数量；

全局变量

这些变量可以设置成全局变量，也可以作为参数传给 dfs，区别在于恢复现场时采取的措施不同；

设置函数

编写代码

组合

题目解析

算法原理

解法 : 暴搜

决策树

根据题目示例可以知道，得到的 path ，元素没有顺序可言，path 的区别只在元素的种类，所以可以画出决策树：

1. 两层节点代表的数相同，执行紫色剪枝；
2. 前面的分支已经枚举过这种可能，执行蓝色剪枝， path 只看元素种类，不看元素顺序

发现规律

所以我们不需要定义全局变量来剪枝，只需要在向下递归时，从当前节点元素的下一个元素开始递归即可；

设置函数

编写代码

目标和

题目解析

算法原理

解法

决策树

这棵决策树是要深度优先遍历的，每一个节点每次递归只能遍历一条分支，而不是在一个节点递归时，同时记录所有分支；通过递归回溯相结合的方式，遍历整棵决策树；

编写代码

path 是全局变量时候的代码（手动回溯）

path 作为参数的代码（自动回溯）

报错原因：

如果我们提前让 path+= nums[i] ，是真正修改了 path 的状态并且记录，那么编译器在帮我们恢现场的时候，只会恢复 pos 的值，而因为 path 的值无法恢复到上次递归前的值；

组合总和

题目解析

算法原理

解法一：暴搜

决策树

红色剪枝：剪去超过 target 的分支

紫色剪枝：剪去重复出现的组合

最终结果

发现规律

从最终的有效递归图，我们可以发现，有效递归都是是从当前节点开始，向后枚举的；

所以我们在进行下一轮递归时，从当前节点开始枚举即可；

编写代码

报错原因：没有考虑以 pos 越界的情况作为递归出口，并且忽略了本题是可以选择重复元素的：

恢复现场的操作是去掉最后一个元素，并且remove() 的 API 也用不对；

解法二

决策树

这棵决策树是的每一层，是在节点和<= target 时，枚举重复元素相加的个数，直到枚举的节点和大于 target；

处理细节问题

(1) 恢复现场的时机

这个解法有一个特别容易被忽略的地方，就是回溯现场的时机，如左下角的两次递归回溯：

第一次回溯，是不能恢复现场的，因为第二次递归，是在第一次递归了0个5的基础上，再多递归1个5；也就是说，对于同一层回溯，只有递归完一个元素能枚举的所有使用次数，才能恢复现场；

并且，恢复现场时，sum 会自动恢复，但是 path 需要我们手动恢复；

(2) 在解法一的基础上修改代码

对于解法二，只是枚举的策略不同，其他的递归，剪枝操作和解法一是相同的；因此，我们只需要删除红色框的代码，在此基础上重新编写即可；

(3) 用于枚举的循环的终止条件

这个循环的小细节是，枚举 nums[pos] 的个数是从0个开始的，当 k* nums[ pos ] > aim，枚举完这个数的所有可能的使用个数：

(4) 在哪里恢复现场？

不要在上面 for 循环恢复现场，出了 for 循环，表示 nums[pos] 的使用个数枚举完毕，此时再恢复现场：

(5) 恢复现场的循环起点

注意：恢复现场的循环从 k=1 开始

因为我们在递归枚举时，会枚举 nums[pos] 使用0次的情况（上层 for 循环从 k=0 开始循环）：

但是 path 真正添加 nums[pos] 时，nums[pos] 的使用次数是不为0的；所以我们恢复现场要从 k=1 开始；

所以我们手动恢复现场，本质上恢复的的是执行 path.remove(size()-1) 操作 k-1 次，sum 则是因为通过参数传递，编译器会自动帮助我们恢复 sum ；