448，组合的几种解决方式

Original 山大王wld 数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

We are all in the gutter, but some of us are looking at the stars.

身在井隅，心向璀璨。

问题描述

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

示例:

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

回溯方式解决

这题要求的是从n个数字中选出k个弄成一组合，问最后总共有多少种组合，其实我们可以把它看做是一棵n-k+1叉树，比如n=4，k=2，那么就是一颗3叉树，这里以示例为例画个图看一下。

注意这里只能选择后面的数字不能选择前面的数字，比如我选择了2，就能在选择1了，否则就会出现[1，2]和[2，1]这种重复的组合，同理我选择了3，那么1和2都不能再选了因为如果再选就会出现重复。

n叉树的遍历还记得吗

 1private void backtrack() {
 2    if ("终止条件") {
 3        return;
 4    }
 5
 6    for (int i = ?; i <= n - k + 1; i++) {
 7        //逻辑运算1，（可有可无，视情况而定）
 8
 9        //递归调用，遍历每一个分支
10        backtrack(list, n, k - 1, i + 1, tempList);
11
12        //逻辑运算2，（可有可无，视情况而定）
13    }
14}

我们来看下上面的框架，逻辑运算1的时候，就表示沿着当前分支走下去，我们把当前选择的值添加到集合中。逻辑2表示这个分支走完了我们要跳到另一个分支，之前讲426，什么是递归，通过这篇文章，让你彻底搞懂递归的时候提到过，从一个分支跳到另一个分支的时候，要么之前分支在运算之前先复制一份，要么把当前分支添加的值给移除，否则会造成分支污染。这两种方式都可以，但后一种效率会更好，他不会大量的复制数据。那么终止条件是什么呢，就是集合中的数据大小为k的时候，就表示找到了一组组合。搞懂了这一点代码就比较容易写了

 1public List<List<Integer>> combine(int n, int k) {
 2    List<List<Integer>> list = new LinkedList<>();
 3    backtrack(list, n, k, 1, new ArrayList<>());
 4    return list;
 5}
 6
 7private void backtrack(List<List<Integer>> list, int n, int k, int start, List<Integer> tempList) {
 8    //终止条件，找到一组组合
 9    if (k == 0) {
10        list.add(new LinkedList<>(tempList));
11        return;
12    }
13    //注意这里的i不能从0开始，如果从0开始会出现重复的，比如[1，2]和[2，1]
14    for (int i = start; i <= n - k + 1; i++) {
15        //把当前值添加到集合中
16        tempList.add(i);
17        //递归调用
18        backtrack(list, n, k - 1, i + 1, tempList);
19        //从当前分支跳到下一个分支的时候要把之前添加的值给移除
20        tempList.remove(tempList.size() - 1);
21    }
22}

参考二进制位

我们知道二进制位中，每个位置有两种状态，一种是0一种是1，这里也可以参照位运算的表示方式，每个数字都有选和不选两种状态，具体画个图来看下

 1public List<List<Integer>> combine(int n, int k) {
 2    List<List<Integer>> list = new ArrayList<>();
 3    backtrack(list, n, k, 1, new ArrayList<>());
 4    return list;
 5}
 6
 7private void backtrack(List<List<Integer>> list, int n, int k, int start, List<Integer> tempList) {
 8    //终止条件，找到一对组合
 9    if (k == 0) {
10        list.add(new ArrayList<>(tempList));
11        return;
12    }
13    if (start <= n - k) {
14        //不选当前值，k不变
15        backtrack(list, n, k, start + 1, tempList);
16    }
17    //选择当前值，k要减1
18    tempList.add(start);
19    backtrack(list, n, k - 1, start + 1, tempList);
20    //因为是递归调用，跳到下一个分支的时候，要把这个分支选的值给移除
21    tempList.remove(tempList.size() - 1);
22}

递归方式解决

这题要求的是从n个数字中选出k个弄成一组合，问最后总共有多少种组合，如果用数学知识就是C(n,k)，这个公式又可以表示为C(n,k)=C(n-1,k-1)+C(n-1,k)，也就是说要么选第n个数字，要么不选第n个数字。

（1），选第n个数字

如果选第n个数字，我们需要从前面n-1个数字中选择k-1个，然后在和数字n组合

（2），不选第n个数字

如果不选第n个数字，我们可以直接从前面n-1个数字中选择k个即可

那么最终的结果就是上面两种的和，我们来直接看下代码

 1public List<List<Integer>> combine(int n, int k) {
 2    List<List<Integer>> res = new ArrayList<>();
 3    //边界条件判断
 4    if (n < k || k == 0)
 5        return res;
 6    //不选择第n个，从前面n-1个数字中选择k-1个构成一个集合
 7    res = combine(n - 1, k - 1);
 8    //如果res是空，添加一个空的集合
 9    if (res.isEmpty())
10        res.add(new ArrayList<>());
11    //然后在前面选择的集合res中的每个子集合的后面添加一个数字n
12    for (List<Integer> list : res)
13        list.add(n);
14    //res中不光要包含选择第n个数字的集合，也要包含不选择第n
15    //个数字的集合
16    res.addAll(combine(n - 1, k));
17    return res;
18}