注意：
整体思路清晰，回溯的过程大概是怎样的每层递归实际上要解决的问题是什么一定记住，该重置的状态要重置，因为回溯就是相当于在每一层的递归中做选择，选择了不同的选项，在遇到阻碍或者达到条件结束递归之后，再想尝试其他的选择路径，应当记住回退到之前的状态。纵向：递归的深度，完整地解决问题（搜索完所有的方案/找到最优方案 ）所必须完成地一整个连续过程，该过程的长度。例如，在“选/不选”递归（0/1递归）中，递归的深度是可选值的数量。
对于纵向思维，要有层层深入，逐渐解决问题的概念。对于横向思维，其实就是从并列的多个选项中选择一个出来加入当前的方案，或者说是在岔路口选择一条路.... 它只是考虑在当前的路口（某层的递归状态中）解决了当前的问题。而不管可选项再多，只能从中选择一个，对于整个递归路径来说，也只是解决了当前的一个问题而已。
横向：每一层递归考虑的选择范围，有多个选项，并且只能从这多个并列选项中选择一条。例如： “选/不选”递归（0/1递归）；在网格中寻找路径的题目中，每一层的递归可以考虑的选择范围是“上下左右”四个方向。
小结： 把回溯问题当做是闯关游戏，纵向就是游戏进度在不断的前进，而横向就是每一关中自己做的不同选择，做了不同的选择就会走在不同的闯关路径上，我们要不就是（1）在目前的闯关路径上一闯到底（完成一次合格的搜寻，如果是最优问题，可能已经找到了解；如果是要给出所有可能的解，我们在记录了合格解后，还需要回溯重置，再选择不同的路径重新探索）（2）要不就是领盒饭（因为一些限制条件，提前终止），然后回溯重置，再选择不同的路径重新探索。
-----------------------------------------------------------------------------------------
人生，却不能像回溯一样，回退重选。在某个状态下即使面临很多选择，我们也只能从中选择一个，然后继续往前走，关于限制条件，它本身不能让我们强制领盒饭，不过却可以改变甚至重塑我们的生活和精神状态。
而因为我们的时间线是永远一个方向延申的，实际上我们永远都是在纵向路径上前进，且还是时间有限的路径上。
想要拥有更加丰富的人生体验，也只有在路上多增设一些路口了，把那些没有尝试的横向选项收纳进来，emm......是这样吧
------------------------------------------------------------------------------------------
（1）这几类问题都是有一组可选值，我们需要考虑每一个值选/不选这两种状态。那么，自然的递归式想法就是：我们对每一个可选值，选/不选它 ，再进入下一层递归（即考虑另一个可选值的选择状态）。
如何控制遍历每一个可选值呢？
递归深度 对应于 可选值的遍历
也就是，在每层递归里我们做的就是：
77 组合
/** * 77. 组合 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] */ // 使用回溯，可以有两种思路 // 1. 思路一：对于每一个数选/不选（0/1）往深层递归， // 最长的递归深度等于n（即最开始有哪些数可以选择）， // 在递归的过程中如果遇到满足解的要求（path的长度等于k）， // 则将合法解加入res解集（即记录合法解）。 class Solution { List<List<Integer>> res = new ArrayList<List<Integer>>(); // 里层的尖括号里面必须要是List // 不能是ArrayList List<Integer> path = new ArrayList<Integer>(); public List<List<Integer>> combine(int n, int k){ dfs(1, n, k); return res; } public void dfs(int cur, int n, int k){ //记录合法的答案 （这两个if语句的顺序很重要！） if(path.size() == k){ res.add(new ArrayList<Integer>(path)); // 要重新new一个， // 否则指向的可变的path对象 return; } //没有可选，结束递归 if(cur == n + 1) return; //选择当前数 path.add(cur); dfs(cur + 1, n, k); //回溯，重置状态 path.remove(path.size() - 1); //不选择当前数，进行递归 dfs(cur + 1, n, k); } } // 2. 思路二：递归深度是k，在每一层递归中从可以选择的数的集合中选择一个数 // 在递归的过程中如果遇到满足解的要求（path的长度等于k）， // 则将合法解加入res解集（即记录合法解）。 class Solution { List<List<Integer>> res = new ArrayList<List<Integer>>(); List<Integer> path = new ArrayList<Integer>(); public List<List<Integer>> combine(int n, int k) { dfs(n, k, 1); return res; } void dfs(int n, int k, int cur){ if(k == 0){ res.add(new ArrayList<Integer>(path)); return; } for(int i = cur; i < n + 1; i++){ path.add(i); dfs(n, k - 1, i + 1); //！！！！注意这个地方是i+1而不是cur+1 //好好思考这是为什么！ //这是组合问题！为了避免重复 path.remove(path.size() - 1); } } }78 子集
/*** 78. 子集 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明：解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] */ // 有两种回溯思路： // 思路1： class Solution{ List<List<Integer>> res = new ArrayList<List<Integer>>(); List<Integer> path = new ArrayList<Integer>(); public List<List<Integer>> subsets(int [] nums){ dfs(nums, 0); return res; } // 明确每一层递归函数里面解决的是： // nums数组中每一个可选值，选/不选----> // 所以递归结束的条件就清楚了， // 在没有其他的要求的情况下（77中有k的限制，可以提前终止）， // 结束递归就是nums中所有的可选值都被考虑过，即cur==nums.length public void dfs(int [] nums, int cur){ if(cur==nums.length){ res.add(new ArrayList<Integer>(path)); // ！！！不同于思路2在进入递归一开始就记录合法解 // 这种思路只有在if语句内才能得到合法解，才能记录合法解； // 否则res中会出现重复的合法解 return; } path.add(nums[cur]); dfs(nums, cur + 1); path.remove(path.size() - 1); dfs(nums, cur + 1); } } // 思路2： class Solution { List<List<Integer>> res = new ArrayList<List<Integer>>(); List<Integer> path = new ArrayList<Integer>(); public List<List<Integer>> subsets(int[] nums) { dfs(nums, 0); return res; } void dfs(int[] nums, int cur){ res.add(new ArrayList<Integer>(path)); // 一进入每层递归，就得到一个合法解， // 就记录合法解 for(int i = cur; i < nums.length; i++){ path.add(nums[i]); dfs(nums, i + 1); path.remove(path.size() - 1); } } }90 子集II
46 全排列
class Solution { List<Integer> path = new ArrayList<Integer>(); List<List<Integer>> res = new ArrayList<List<Integer>>(); public List<List<Integer>> permute(int[] nums) { dfs(nums, 0); return res; } void dfs(int[] nums, int cur){ if(cur == nums.length){ res.add(new ArrayList<Integer>(path)); return; } for(int i = cur; i < nums.length; i++){ path.add(nums[i]); swap(nums, cur, i); dfs(nums, cur + 1); path.remove(path.size() - 1); swap(nums,cur, i); // 回溯一定要己得这里重置可选集状态!!! } } void swap(int[] nums, int cur, int i){ int t = nums[cur]; nums[cur] = nums[i]; nums[i] = t; } }47 全排列II
