image-20210910111436576.png

1.理解题目

正如题目所说这是一个组合问题，相信大家也都不陌生了，就相当于是在n个不同的小球中选出k个，写出所有的组合，当然高中一般是让我们求出组合数，那这里是要我们求出所有的可能，那对这种题是没有更好的解法的，只能穷举出所有的可能。

2.解题思路

2.1.for循环遍历

最简单的方法，当然就是用for循环遍历，一个元素一个元素，列举就行了。

当k等于2时：

  1. int n = 4;
  2. for (int i = 1; i <= n; i++) {
  3.     for (int j = i + 1; j <= n; j++) {
  4.         res.add(Arrays.asList(i, j));
  5.     }
  6. }

当k等于10时:

  1. int n = 20;
  2. for (int i = 1; i <= n; i++) {
  3.     for (int j = i + 1; j <= n; j++) {
  4.         for (int k = j + 1; k <= n; k++) {
  5.             for()
  6.                 ...
  7.         }
  8.     }
  9. }

这岂不是要写10个for循环，确实，for循环是可以帮助我们穷举遍历，但是按照这样的方法来写，k必须要确定，而且k只有在较小的时候才容易写，一旦多起来根本没有办法写。

2.2.回溯

这个时候就要使用回溯搜索的方法了，我们知道for循环是可以写成递归的形式的，利用递归的方法来代替上面for循环，所以说回溯其实也是穷举的方式，只不过更容易写了。

先让我们想想for循环是怎么个穷举的

组合.jpg

是的，就像一棵树一样，不断往下面走，直到最内层的循环为止，然后返回上一层循环，遍历完后，又返回上一层循环。这个过程和递归不也是一样的吗？不断地调用自身，从顶到底，再一层层地返回。其实回溯就是dfs，先从一个一直搜索到最后，在返回一层再搜索，直到将所有都遍历完。我们可以把回溯的问题都抽象成一棵n叉树，然后就是深度优先遍历。

List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();

public List<List<Integer>> combine(int n, int k) {
    backtracking(n, k, 1);
    return res;
}

void backtracking(int n, int k, int startIndex){
    //base case
    if(path.size() == k){
        res.add(new ArrayList<>(path));
        return;
    }
    for(int i = startIndex; i <= n; i++){
        path.add(i);
        backtarcking(n, k, i+1);
        //回溯
        path.remove(new Integer(i));
    }
}

上面的res是用来返回结果集的，path用来保存遍历过的元素，因为要到最后终止的时候才能出结果，所以要保存下路径，不像for循环每层的变量会记录路径，递归也需要一个东西来保存路径。

其中有两个点需要注意：

  • res添加的时候，需要重新复制一份路径
  • 对用ArrayList的remove方法有一个坑，有两个重载的remove方法，一个是按下标remove(int index)，一个是按值remove(E e)，现在我要删除的是元素i，而不是按下标删除，所以就会出现问题。我们以为用的是第二个，但实际是第一个，它并不会自动装箱，所以我们要手动转成包装类Integer