【算法题解】29. 组合的递归解法

这是一道 中等难度 的题

https://leetcode.cn/problems/combinations/

题目

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2 
输出： [
        [2,4], 
        [3,4], 
        [2,3], 
        [1,2], 
        [1,3], 
        [1,4],
      ]
1
2
3
4
5
6
7
8
9

示例 2：

输入：n = 1, k = 1 
输出：[[1]]
1
2

提示：

• $1<=n<=20$
• $1<=k<=n$

题解

这道题的解题思路和 子集 是一样的，每个数都有 选 和 不选 两个选项。

但这个题目限定了组合（也就是子集）的长度为 k ，所以需要在最后判断一下只有子集 subSet 的大小为 k 的时候才能计入答案。

另外这题有个可以优化的点：
如果当前子集 subSet 的大小 加上 剩余的所有数字 都还小于 k , 那么这个分支就可以剪掉，因为即使走到最后一步也无法满足条件。

Java 代码实现

class Solution {
    private List<Integer> subSet = new ArrayList<>();
    private List<List<Integer>> ans = new ArrayList<>();
    
    public List<List<Integer>> combine(int n, int k) {
        recursion(1, n, k);
        return ans;
    }

    private void recursion(int i, int n, int k){

        // 当已经选够了 k 个数的时候，后面就不需要计算了
        if(subSet.size() == k){
            ans.add(new ArrayList(subSet));
            return;
        }

        //当剩下的数全部选上都不够k个的时候，直接返回。
        if(subSet.size() + (n - i + 1) < k){
            return;
        }

        // 不选
        recursion(i + 1, n, k);


        // 选
        subSet.add(i);
        recursion(i + 1, n, k);
        subSet.remove(subSet.size() - 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

Go 代码实现

var ans [][]int
var subSet []int

func combine(n int, k int) [][]int {
    subSet = []int{}
    ans = [][]int{}

    recursion(1, n, k)

    return ans

}

func recursion(i int, n int, k int) {
    if k == len(subSet) {
        temp := make([]int, len(subSet))
        copy(temp, subSet)
        ans = append(ans, temp)
        return
    }

    if (len(subSet) + (n - i + 1)) < k {
        return
    }

    // 不选
    recursion(i + 1, n, k)

    // 选
    subSet = append(subSet, i)
    recursion(i + 1, n, k)
    subSet = subSet[:len(subSet) - 1]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33