回溯

组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

• 思路：一道回溯的经典题目，回溯也有三部曲，确定递归函数的返回值和参数，确定终止条件，确定单层搜索过程
  ，回溯思路的建立可以是按照树的形式进行，在终止处统计需要的返回值，每次递归就是树的深度更深一层，树的宽度就是
  循环的次数。所以这道题以n为循环次数，循环内部先将循环遍历的当前值加入路径中，然后往下一层递归，直到递归到所谓叶子节点
  ，进行结果的统计并返回，之后就是回溯清除，进行下一次循环。

组合plus

给定两整数，在1-9之间找相加和为n的k个数组合。每个数唯一，返回组合列表

• 思路：回溯，1-9是循环的宽度，也就是树的宽度，起始索引从1开始，然后每次其实索引递增往深处遍历，遍历之前将目前索引加入路径之中
  直到满足条件，就返回结果值，下来是修枝，当总和大于目标值后，修枝，当总数大于目标数后，修枝。

• 

电话号码的字母组合

每个电话号码对应着一组字符，现在给定号码的组合，返回号码对应字母的组合，长度为号码组合的长度

• 思路 想办法和回溯连接起来，也就是想办法搭建一棵树，树的水平层面，也就是树的宽度，就是一个号码对应的字符串长度，
  树的深度，就是号码组合的长度，所以和回溯一样，遍历第一层，然后将这层对应数值加入到结果队列中，递归下一层，递归完了就删除结果队列最后一个，进行宽度的下一个

组合总和

给了无重复数组，以及目标值，要求返回数组内和为目标值且数可以重复组合

• 思路： 组合问题，联想到回溯，数组长度为树的宽度，不断递归找下一个数为深度，因为是无限制的取，所以每次遍历宽度都是遍历整个数组。

组合总和2

现在是不允许重复，即便数组中有重复元素，且每个元素只允许使用一次。

• 思路 ： 在上一道题目的基础上，加上是否用过的标签，这个标签可以用一个布尔类型的数组存放，然后再加一个判断条件
  ，如果这个数与上一个数一样且没有遍历过，就忽略它，然后每次回溯标签值也要回溯回去。

分割回文字符

给一串字符，分割并且要求分割后的每一个字符为回文字符

• 思路：分割问题，回溯，字符宽度为循环次数，循环内，先进行结果的记录，然后判断是否回文，回文的话就可直接将结果保存，递归找下一个回文，不是就进行下一次循环。
  思考疑惑的点是存放结果咋存放，首先是分析返回结果格式，为列表里套列表，然后套字符串，所以先串字符串，然后保存到列表中，再然后将列表保存到列表中。
  

复原ip地址

给一串字符串，分割出有效的IP地址来，分割处用’.’分隔。

• 思路： 还是分割问题，第一次遇到的难点在于不知道怎么拼接合适，其实可以借助下标，整个字符没变，不管是判断字符是否合规还是拼接字符。然后就是截止条件，设置为字符全部遍历完（
  索引标跑到字符末尾），且数量为4，字符是否合规写在循环条件里，利用stringbulider拼接，回溯的话，删除sb里索引对应的位置。

返回数集组合

给一个数组，返回数组内任意不重复的组合合集。

• 思路： 组合问题，但是这个是每个节点都要记录，所以还是回溯，每遍历一个新节点，就将其记录下来。

子集

给一个整数数组，返回可能的子集，但是不能包含重复元素

• 思路： 在上一道上面的改编，加一个剪枝的条件，就是如果当前将要遍历的值与上一次遍历值相同，就无需继续递归了。

非递减子序列

给一个整数数组，返回数组中不同的递增子序列，且至少有两个元素。

• 思路：回溯，记录的条件是大于等于两个元素，在此基础上新加条件，判断是否有序且不重复。

全排列

给一个不含重复数字的整数组，返回所有可能的排列组合。

• 思路：还是组合问题，在叶子节点处记录

全排列

这次是包含了重复数字的数组

• 思路：组合问题，然后需要判断是否重复使用，这样就借助重复使用标记数组，每次数被记录使用后，标记数组对应值也更新，回溯后数被删除，同样更新数组。