编程语言算法
递归搜索与回溯算法详解及综合练习
本文通过多个 LeetCode 例题（子集异或和、全排列 II、电话号码组合、括号生成、组合、目标和、组合总和、字母大小写全排列），深入讲解递归、搜索与回溯算法的核心思想。重点阐述了决策树的构建、剪枝策略（如重复元素处理、合法分支判断）以及代码实现细节。文章对比了不同解题思路，分析了全局变量与参数传递的区别，并提供了完整的逻辑推导过程，帮助读者掌握回溯算法的综合应用。
本文通过多个 LeetCode 例题（子集异或和、全排列 II、电话号码组合、括号生成、组合、目标和、组合总和、字母大小写全排列），深入讲解递归、搜索与回溯算法的核心思想。重点阐述了决策树的构建、剪枝策略（如重复元素处理、合法分支判断）以及代码实现细节。文章对比了不同解题思路，分析了全局变量与参数传递的区别，并提供了完整的逻辑推导过程，帮助读者掌握回溯算法的综合应用。
这种决策使得每一次递归都是有效的递归，每一个节点都是最终的结果，所以这棵决策树是不用剪枝的，也没有递归出口。
决策树执行添加元素的操作前，要先从子集末尾元素在 nums 的位置后面是否还有元素，如果有元素则可以添加，反之，则不可以添加。
开始时，子集是空集，所以异或的结果为 0，path 初始值刚好是 0，所以不用处理子集为空的情况。
在递归到决策树的某一层时，要知道从 nums 的哪个元素开始向后枚举，因此设计 dfs(nums, pos)。
虽然没有写 return 来回溯，但是在每次向下递归新一层的 dfs 时，这层 dfs 执行完，就会自动返回上一层的 dfs。
这道题其实就是全排列 I 的进阶版本，只是多了重复的数，大体框架和全排列 I 相同，只是剪枝操作需要更细致一点。
本质相同，都是针对是否需要剪枝的情况作出相应的处理。
红色剪枝条件 check[i] == true，表示同一个数只能使用一次。
粉色剪枝条件 nums[i] == nums[i - 1]，表示同一个节点的所有分支中，相同数只能使用一次。
如果我们要全排列的数组是 [1, 2, 1, 3, 1]，那么无法判断同一个节点，其中一条分支要递归的数，是否在前面分支中已经出现过了。
我们可以在正式递归之前，先对 nums 数组先进行排序，方便后续的剪枝操作。在大多数情况下，排序数组的时间复杂度 O(N log N)，对于递归 O(2^N) 来说可以忽略不计。
nums[i] == nums[i - 1] 这个对不合法分支的判断条件范围还是太广了，无法筛查掉红色剪枝的分支，和合法分支（不应该被剪枝的分支）相邻的情况。
因为这些分支所代表的数是相同的，所以 nums[i] 所在的分支会被识别为不合法分支，而被执行粉色剪枝。
但是实际上，被红色剪枝的 nums[i - 1] 所在分支，本身就是不合法分支。
只有当 nums[i-1] 和 nums[i] 两条分支都是合法的时候，才需要判断 nums[i] 是否等于 nums[i - 1]。
我们要把下面这两种情况区分开：
那么怎么区分开呢？其实非常简单；就是判断两个数是否在决策树的同一层。
(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] 所在分支不合法。
只关心不合法分支的最终判断条件：i != 0 && check[i] == false && nums[i] == nums[i-1]
如果我们的思考链路是只关心分支合法，那么第一步就是检查该分支是否被红色剪枝：
所以第一步就是判断 check[i] == false。
合法分支是一条不被执行红色剪枝 && 不被执行粉色剪枝 的分支，所以在判断该分支不被执行红色剪枝后，我们就需判断该分支是否被执行粉色剪枝。
我们先来分析下面这条分支，在检查完 check[i] == false 而不被执行红色剪枝之后，我们来判断是否被粉色剪枝：
显然，nums[i] != nums[i - 1]，因此肯定不会执行粉色剪枝（nums 已经提取排好序了）。
此时的判断条件为 check[i] == false && (nums[i] != nums[i-1]...)
如果 nums[i] == nums[i - 1]，但是 nums[i - 1] 已经被使用过了，此时 check[i - 1] == true，那么此时的分支也是合法的。所以此时的判断条件：
如果只是考虑当前分支是否合法，那么 i 是可以等于 0 的。
i = 0 表示的是数组第一个元素，只要确保 check[0] == false，就一定是可以大胆枚举的；因为这是对 nums 的第一个元素进行枚举的分支，这条分支必定是合法分支（一定是从考虑合法分支的角度出发）。
此时的判断条件：
如果考虑当前分支不合法，就需要根据前一条分支的具体情况，来对当前分支的合法与否作出判断，如果当前分支的 i=0，则会出现数组越界。
定义两层 for 循环，对字符映射的数字的所有组合进行暴力枚举；但是如果一个字符映射的数字过多，使用暴力枚举是不好操作的。
对决策树进行一次深度优先遍历，在叶子节点收集结果即可。
我们可以使用字符串数组，让字符串数组前两个位置空着，让下标为 2 的数组元素存 "abc" 这个字符串，往后依此类推。
我们在遍历原始字符串的时候，拿到字符 '2' 之后，减去字符 '0' 对应的 ASCII 码值，就可以对应字符串数组的下标元素。
给一个括号子串，必须从头到尾遍历子串的每一个括号字符，如果在遍历的过程中，出现左括号的数量大于右括号的数量，那么这个子串就一定不是有效括号子串。
蓝色剪枝表示添加 ( 数量大于 n 剪枝；紫色剪枝表示添加 ) 数量大于 ( 的数量。
这些变量可以设置成全局变量，也可以作为参数传给 dfs，区别在于恢复现场时采取的措施不同。
根据题目示例可以知道，得到的 path，元素没有顺序可言，path 的区别只在元素的种类，所以可以画出决策树：
- 两层节点代表的数相同，执行紫色剪枝；2. 前面的分支已经枚举过这种可能，执行蓝色剪枝，path 只看元素种类，不看元素顺序
所以我们不需要定义全局变量来剪枝，只需要在向下递归时，从当前节点元素的下一个元素开始递归即可。
这棵决策树是要深度优先遍历的，每一个节点每次递归只能遍历一条分支，而不是在一个节点递归时，同时记录所有分支；通过递归回溯相结合的方式，遍历整棵决策树。
报错原因：
如果我们提前让 path+= nums[i]，是真正修改了 path 的状态并且记录，那么编译器在帮我们恢复现场的时候，只会恢复 pos 的值，而因为 path 的值无法恢复到上次递归前的值。
红色剪枝：剪去超过 target 的分支
紫色剪枝：剪去重复出现的组合
从最终的有效递归图，我们可以发现，有效递归都是从当前节点开始，向后枚举的。
所以我们在进行下一轮递归时，从当前节点开始枚举即可。
报错原因：没有考虑以 pos 越界的情况作为递归出口，并且忽略了本题是可以选择重复元素的：
恢复现场的操作是去掉最后一个元素，并且 remove() 的 API 也用不对。
这棵决策树是的每一层，是在节点和 <= target 时，枚举重复元素相加的个数，直到枚举的节点和大于 target。
这个解法有一个特别容易被忽略的地方，就是回溯现场的时机，如左下角的两次递归回溯：
第一次回溯，是不能恢复现场的，因为第二次递归，是在第一次递归了 0 个 5 的基础上，再多递归 1 个 5；也就是说，对于同一层回溯，只有递归完一个元素能枚举的所有使用次数，才能恢复现场。
并且，恢复现场时，sum 会自动恢复，但是 path 需要我们手动恢复。
对于解法二，只是枚举的策略不同，其他的递归，剪枝操作和解法一是相同的；因此，我们只需要删除红色框的代码，在此基础上重新编写即可。
这个循环的小细节是，枚举 nums[pos] 的个数是从 0 个开始的，当 k * nums[pos] > aim，枚举完这个数的所有可能的使用个数：
不要在上面 for 循环恢复现场，出了 for 循环，表示 nums[pos] 的使用个数枚举完毕，此时再恢复现场：
注意：恢复现场的循环从 k=1 开始
因为我们在递归枚举时，会枚举 nums[pos] 使用 0 次的情况（上层 for 循环从 k=0 开始循环）：
但是 path 真正添加 nums[pos] 时，nums[pos] 的使用次数是不为 0 的；所以我们恢复现场要从 k=1 开始；
所以我们手动恢复现场，本质上恢复的的是执行 path.remove(size()-1) 操作 k-1 次，sum 则是因为通过参数传递，编译器会自动帮助我们恢复 sum；
我们可以在原字符串 s 上操作，当 s 递归到叶子节点时，把叶子节点的 s 添加到 ret 中；也可以定义一个全局变量 path，遍历到 s 字符串的字母字符时，就把变或不变的字符（每次只能选一个）添加到 path 上，如果遍历到的是数字，直接添加到 path 后即可。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online