回溯法第一波总结，已经总结了回溯法的基本操作，及程序描述套路。第二波讲一讲一些具体情况。分别从力扣上以下八道题进行总结。
对于递归传入参数理解（有for循环）：（仅代表个人理解）
可能一下子很疑惑，看不懂，为啥有时候传入index+1，i，i+1，有啥区别呢？
1.index+1，表示还会去遍历当前元素前面的元素及当前元素。
2.i，表示一直递归当前元素，直到不能递归时，传入下一个元素
3.i+1，表示一直传入当前元素的下一个元素，它不会再去遍历之前的元素了（和index+1的区别）
题目：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
解题思路：
如下图所示，解题思路是先通过数字字符去对应字符串，然后从每个字符串中提取一个字母进行组合。
all station：需要一个全局的index去遍历每一个字符串，并且for循环是从每个字符串的第一个位置开始走起，与index无直接联系。(是不需要去重剪枝的)
结束条件：当index == 最后一个数字字符对应的字符串。这里不需要别的结束条件，当for循环结束时，自然而然都结束了。
题目：
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3 输出：[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
解题思路：
通过左右括号不断填充的形式。
all station：分为两种情况：1.填入‘（’，进行回溯；2.填入‘）’，进行回溯
结束条件：当分配的括号数到达2n的时候结束
题目：
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。 解集不能包含重复的组合。 示例 :
输入: candidates = [2,3,6,7], target = 7 , 所求解集为: [ [7], [2,2,3] ]
解题思路：
题目说数组中的数可以重复选择。所以要如下图进行遍历。
all station：先将目标值减一个元素减到0或者负数，再回溯，去减第二个元素，以此类推。所以需要一个全局index，去初始化for循环中的i，再次递归的时候index的参数应为上一个的i。（因为数组不重复，所以也不需要去重剪枝）
边界条件：当target<0的时候，说明减过头了
结束条件：target == 0时，将temp压入res即可
题目：
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。 示例 :
输入: candidates = [10,1,2,7,6,1,5] , target = 8 , 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
解题思路：
和上一题类似，因为远数组有重复元素，下图为重复元素产生的原因，以数组{1,2,2,3,4,}为例，第二层第一次是第一个2，，第二层的for循环第二次就会遍历到第二个2，所以就产生了同层重复。所以需要考虑两个情况：1.去重；2.如何遍历
all station：使用for循环进行遍历，需要一个全局index作为i的初始值。每次递归传入的参数是i+1。由于同一层的重复元素（组合不能重复），所以需要去重，if(i-1 >= start && candidates[i] == candidates[i-1]) continue;
边界条件：当target<0时，return
结束条件：当target == 0时，将temp压入res；return
题目：
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]解题思路：
递归交换顺序如下图所示，左边表示index，右边表示i。因为数组中无重复元素，所以不需要去重。
all station:使用for循环进行遍历，使用index初始化i。使用index+1作为下次递归的参数。因为上一次的递归是index+1之前的数值，所以不需要对index-1操作。
结束条件：当index==nums.size()的时候，说明交换完了
题目：
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]解题思路：
本题在上一题的基础上做了修改，允许数组有重复元素。那么需要考虑去重问题。
all station：使用for循环，利用index进行i的初始化。和上题一样。这里需要考虑去重问题，去重只要考虑begin到i之间有没有重复的元素，因为i是在begin的基础上往后移动，那么当有出现重复元素的话，说明之前和begin所在元素交换过了，就不需要交换了
结束条件：index == nums.size()
题目：
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4 输出: [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ] 解释: 4 皇后问题存在两个不同的解法。
题目解析：
N皇后是在全排列的基础上进行的。先建立一个数组进行0~n-1赋值，将这个数组全排列，找到符合条件的全排列即可。
all station：利用index对for循环中的i进行初始化，交换nums[i]和nums[index]。将index+1作为下一次递归的参数。
结束条件：当index == nums.size()的时候，进行排列check。check的条件为abs(i-j) == abs(nums[i]-nums[j]);也就是当前皇后距离下一个皇后的宽度和高度相等时，说明在斜对角线上，是不符合条件的。因为数组全排列，保证所有的皇后不会出现在同一行列。
题目：
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
示例:
输入: 4 输出: 2 解释: 4 皇后问题存在如下两个不同的解法。 [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."],
["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ]
题目解析：
与上一题思路一模一样。N皇后是在全排列的基础上进行的。先建立一个数组进行0~n-1赋值，将这个数组全排列，找到符合条件的全排列即可。
all station：利用index对for循环中的i进行初始化，交换nums[i]和nums[index]。将index+1作为下一次递归的参数。
结束条件：当index == nums.size()的时候，进行排列check。check的条件为abs(i-j) == abs(nums[i]-nums[j]);也就是当前皇后距离下一个皇后的宽度和高度相等时，说明在斜对角线上，是不符合条件的。因为数组全排列，保证所有的皇后不会出现在同一行列。
难度：中等
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]题目解析：
显然使用回溯法，仔细分析一下。先建立一个1~n的数组，我们需要一个全局index去作为for循环的初始值。
结束条件：当计数器计到和所要抽取的数字个数相等时结束，将temp压入res
all station：因为题目不要求重复，所以传入给index的值为i+1（因为不需要再去读取前面的元素了），并同时计数+1
难度：中等
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]题目解析：
分析一下，它这个不同长度的组合，那么我们是不是只要调用不同长度的回溯法就行了呢，答案是肯定的。
all station:使用for循环，每次压入元素，将i+1传入下次递归，并且将计数器count+1，也传入下次递归
结束条件：计数器count和阈值相等就结束
难度：中等
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2] 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]题目分析：
在上一题的基础上，元素有了重复，那么就需要去重。当index到i之间有和当前元素重复的元素就无需再选当前元素，因为前面已经选过了（排列在这个重复元素上，也是这个相同的去重（剪枝）方法，因为重复原理都一样）。和上题不一样的是这个阈值是从0~n的，所以需要遍历回溯。
all station：使用for循环，每次压入元素，将i+1传入下次递归，并且将计数器count+1，也传入下次递归
结束条件：计数器count和阈值相等就结束
