这篇page主要是针对leetcode上的77.组合所写的。小尼先简单的给大家说明一下这道题的意思，给出两个整数n和k，返回范围在1到n之间的所有可能k个数的集合，顺序可以随意。这里运用的方法就是回溯法。
小尼今天也根大家系统的说明一下回溯法，回溯法也可以称为回溯搜索法，其实就是一种搜索的方式，其实回溯法也不是什么高效的算法，其实就是一种穷举的写法，回溯法其实就是利用了递归的一种穷举的方法。
接下来说明一下回溯法一般的作用或者说一般用于解决哪些问题：
1、组合问题：N个数里面按照一定规则找出k个数的集合
2、切割问题：一个字符串的按照一定规则有几种切割方式
3、子集问题：一个N个数的集合里有多少符合条件的子集
4、排列问题：N个数按一定规则全排列，有集中排列方式
4、棋盘问题：N皇后、解数独问题。
回溯法解决的问题都可以抽象为树形结构，回溯法解决的都是在集合中的递归查找子集，集合的大小就构成了数的宽度，递归的深度就构成了数的深度。递归就要有终止条件，所以必然是一颗高度有限的数（N叉树）。
我们拿回溯与二叉树做一个比较，我们可以知道递归具有递归三部曲，同样回溯也是具有回溯三部曲，小尼在这里给大家总结一下。首先，第一步就是回溯函数模板返回值以及参数，在回溯算法中，我们需要给我们的函数定义一个全新的类，我们通常给这个类定义的名字叫backtracking，并且函数的返回值我们一般都为void。第二步，就是定义函数的返回值以及参数，在回溯法中，我们给函数定义的名字是bactracking，我们需要看清楚参数，因为回溯算法需要的参数不像二叉树递归的时候那么容易一次性就可以直接定下来，所以我们在写回溯算法的过程中，我们一般是先写逻辑，然后看我们的逻辑中需要些什么参数，然后我们再在我们的方法里加入我们对应的参数。第三步，就回溯函数的终止条件，既然回溯算法是一个树形结构，那么我们在讲解二叉树的递归的时候，我们就知道一定是有终止条件的，所以回溯也要有终止条件，在第三步中我们可以看到，什么时候达到了终止条件，从树中就可以看出来，一般来说是搜到了叶子节点，也就是找到了满足一条答案的值的时候，这个时候我们需要将答案存放起来，并结束本层的递归。
上面我们聊完了额回溯法，接下来我们继续解释我们上面的那道题，小尼接下来给出递归的代码：
class Solution {
List> result = new ArrayList<>();
LinkedList path = new LinkedList<>();
public List> combine(int n, int k) {
change(n,k,1);
return result;
}
public void change(int n,int k,int StartFirst){
if(path.size() == k){
result.add(new ArrayList<>(path));
return;
}
for(int i = StartFirst ; i <= n - (k - path.size()) + 1 ; i++){
path.add(i);
change(n,k,i+1);
path.removeLast();
}
}
}
这上面的代码中，其实是对回溯法进行了一定的减枝，其中减枝的方法的体现就是上面的i<=n-(k-path.size())+1，这一句话小尼在最开始看的时候小尼还没有怎么看懂，但是小尼在看懂了之后小尼才觉得这句话的深度，小尼先简答的说一下这句话的作用就是，当我们的第一个list中放入越来越多的值之后，我们的区间就在不断的减少，然后当我们进行下一层for循环的遍历的时候，我们的循环的次数又会继续的改变，在这里我们在不断的递归的过程中，这一句话最巧妙的地方就是在我们的值不断的往后遍历的过程中会相应的改变，这就达到了减枝的作用。希望今天的知识可以绑帮助到小伙伴们！