77.组合

题目

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combinations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

引入

首先想到的是for循环,k=2使用两层循环,k=3使用三层循环,循环的层数随k的大小增加而增加，显然是很难解决的。
问题的本质还是枚举，此时就考虑回溯法。
原理
每一次递归中嵌套一个for循环，那么递归就可以解决多层循环的问题。

转换

回溯法解决的问题都可以抽象为树形结构

输入n=4，k=2时 每次从剩下的数中选择元素，可选的范围进行收缩 n相当于是树宽，k相当于是树深，叶子节点就是需要的答案 转换之后一个初步的思路就出来了: 1.递归到叶子节点 2.保存节点值到结果集 3.回溯到上一个节点

题解

递归和回溯都是成对出现的，递归函数的三部曲同样适用与回溯。 **递归函数的返回值以及参数** 参数里一定有的是集合n里面取k个数，随着选择数的增加，可选的数减少，就需要一个变量去标识可选区间。 设置startIndex作为标志变量，每一次递归startIndex都要少1

List <List<Integer>> res = new ArrayList<> ();
List<Integer> path = new  ArrayList<> (); //符合条件的单一条件
void backtracking(int n,int k,int startIndex)

递归的终止条件

终止条件就是到了叶子节点，但是这并不是一颗树，只是我们抽象成了一颗树，那么判断叶子节点就不能用左右节点为空来判断了。
根据题意，当path.length=k时，说明找到了大小为k的组合，path存的就是根节点到叶子节点的路径。

if(path.length == k){
res.add(path)
return;
}

单层递归逻辑

通过每一次递归中嵌套一个for循环来达到多层循环的目的。 根据抽象的树状图可以看出来，每一次循环是从startIndex开始，把数组中的数放进单一结果集。 **递归是从根节点往叶节点纵向遍历树，for循环时从左往右横向遍历树**

for(int i=startIndex;i<=n;i++){
path.add(i); //处理节点
//----------错误的-------
//backtracking(n,k, startIndex+1);
backtracking(n,k, i+1);
//到了叶子节点，退出循环，此时需要进行回溯
path.remove(path.size()-1);
}

错误点：startIndex的作用是标识变量，只是起标识作用，循环的过程中控制取值的i

代码

List <List<Integer>> res = new ArrayList<>();
List<Integer> path = new  ArrayList<> ();
public List<List<Integer>> combine(int n, int k) {
if (k <= 0 || n < k) {
    return res;
 }
backtracking(n,k,1);
return res;
}
void backtracking(int n,int k,int startIndex){
if(path.size() == k){
//------------错误点1----------
//res.add(path);
//修改
res.add(new  ArrayList<> (path));
return;
}
for(int i=startIndex;i<=n;i++){
path.add(i); 
//----------错误点2-------
//backtracking(n,k, startIndex+1);
//修改
backtracking(n,k, i+1);
path.remove(path.size()-1);
}
}

错误点1★★★★★: path的类型是List，这是以一个引用类型。
res.add(path)：将res尾部指向了path地址，后续path内容的变化会导致path的变化，那么这里存的永远是最后的空数组。
res.add(new ArrayList(path)):每次添加都重新开辟了一个独立空间,res尾部指向了独立空间，后续path变化不会影响到res。相当于深克隆
参考文章
错误点2：startIndex的作用是标识变量，只是起标识作用标识从哪个数开始取值，真正控制取哪个值的是i