找出所有子集的异或总和再求和
题目解析
算法原理
解法
决策树
这种决策使得每一次递归都是有效的递归，每一个节点都是最终的结果，所以这棵决策树是不用剪枝的，也没有递归出口。
注意
决策树执行添加元素的操作前，要先从子集末尾元素在 nums 的位置后面是否还有元素，如果有元素则可以添加，反之，则不可以添加。
全局变量
开始时，子集是空集，所以异或的结果为 0，path 初始值刚好是 0，所以不用处理子集为空的情况。
函数结构
在递归到决策树的某一层时，要知道从 nums 的哪个元素开始向后枚举，因此设计 dfs(nums, pos)。
编写代码
虽然没有写 return 来回溯，但是在每次向下递归新一层的 dfs 时，这层 dfs 执行完，就会自动返回上一层的 dfs。
全排列 II
题目解析
算法原理
这道题其实就是全排列 I 的进阶版本，只是多了重复的数，大体框架和全排列 I 相同，只是剪枝操作需要更细致一点。
两种剪枝
- 在同一个节点（如图中的黑色节点）的所有分支中，相同的元素只能选择一次：
- 同一个数只能使用一次，可以设置一个 check[] 数组来标记一下用过的数为 true。
完善决策树
两种思考方式
本质相同，都是针对是否需要剪枝的情况作出相应的处理。
只关心不合法的分支（被剪枝的分支）
红色剪枝条件 check[i] == true，表示同一个数只能使用一次。
粉色剪枝条件 nums[i] == nums[i - 1]，表示同一个节点的所有分支中，相同数只能使用一次。
问题一：如果 nums 中重复元素不是连在一起的，那么这个判断条件无法使用
问题解析
如果我们要全排列的数组是 [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 时，访问 nums[i - 1] 会越界
只关心不合法分支的最终判断条件：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 的。
i = 0 表示的是数组第一个元素，只要确保 check[0] == false，就一定是可以大胆枚举的；因为这是对 nums 的第一个元素进行枚举的分支，这条分支必定是合法分支（一定是从考虑合法分支的角度出发）。
此时的判断条件：
两种思考方式判断条件的区别
如果考虑当前分支不合法，就需要根据前一条分支的具体情况，来对当前分支的合法与否作出判断，如果当前分支的 i=0，则会出现数组越界。
处理细节问题
编写代码
只关心不合法分支
只关心合法分支
电话号码的字母组合
题目解析
算法原理
解法一：暴力枚举
定义两层 for 循环，对字符映射的数字的所有组合进行暴力枚举；但是如果一个字符映射的数字过多，使用暴力枚举是不好操作的。
解法二：深度优先遍历
决策树
对决策树进行一次深度优先遍历，在叶子节点收集结果即可。
解决数字和字符串的映射关系
我们可以使用字符串数组，让字符串数组前两个位置空着，让下标为 2 的数组元素存 "abc" 这个字符串，往后依此类推。
我们在遍历原始字符串的时候，拿到字符 '2' 之后，减去字符 '0' 对应的 ASCII 码值，就可以对应字符串数组的下标元素。
全局变量
设计函数
编写代码
括号生成
题目解析
算法原理
给一个括号子串，必须从头到尾遍历子串的每一个括号字符，如果在遍历的过程中，出现左括号的数量大于右括号的数量，那么这个子串就一定不是有效括号子串。
解法：暴搜
决策树
蓝色剪枝表示添加 ( 数量大于 n 剪枝；紫色剪枝表示添加 ) 数量大于 ( 的数量。
全局变量
这些变量可以设置成全局变量，也可以作为参数传给 dfs，区别在于恢复现场时采取的措施不同。
设置函数
编写代码
组合
题目解析
算法原理
解法：暴搜
决策树
根据题目示例可以知道，得到的 path，元素没有顺序可言，path 的区别只在元素的种类，所以可以画出决策树：
- 两层节点代表的数相同，执行紫色剪枝；2. 前面的分支已经枚举过这种可能，执行蓝色剪枝，path 只看元素种类，不看元素顺序
发现规律
所以我们不需要定义全局变量来剪枝，只需要在向下递归时，从当前节点元素的下一个元素开始递归即可。
设置函数
编写代码
目标和
题目解析
算法原理
解法
决策树
这棵决策树是要深度优先遍历的，每一个节点每次递归只能遍历一条分支，而不是在一个节点递归时，同时记录所有分支；通过递归回溯相结合的方式，遍历整棵决策树。
编写代码
path 是全局变量时候的代码（手动回溯）
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 后即可。
全局变量
函数设计
编写代码
