Leetcode 0077.组合

组合

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

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

示例 1：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

示例 2：

1
2


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

提示：

1 <= n <= 20
1 <= k <= n

思路

把组合问题抽象为如下树形结构：

可以看出这棵树，一开始集合是1，2，3，4，从左向右取数，取过的数，不再重复取。

第一次取1，集合变为2，3，4 ，因为k为2，只需要再取一个数就可以了，分别取2，3，4，得到集合[1,2] [1,3] [1,4]，以此类推。

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。

图中可以发现n相当于树的宽度，k相当于树的深度。

图中每次搜索到了叶子节点，就找到了一个结果。

相当于只需要把达到叶子节点的结果收集起来，就可以求得n个数中k个数的组合集合。

代码

Go

 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
34
35
36
37
38
39


package main

var (
    path []int
    res  [][]int
)

//给定两个参数n和k，函数combine返回一个包含所有由1到n中选取k个数字组成的组合的二维数组
func combine(n int, k int) [][]int {
    path, res = make([]int, 0, k), make([][]int, 0)
    dfs(n, k, 1)
    return res
}

//函数使用深度优先搜索（DFS）的方法来生成组合。它通过递归的方式不断构建路径path。
func dfs(n int, k int, start int) {
    //当路径的长度等于k时，就将当前的组合加入结果数组res中
    if len(path) == k { // 说明已经满足了k个数的要求
        tmp := make([]int, k)
        copy(tmp, path)
        res = append(res, tmp)
        return
    }
    //为了避免重复的组合，每次递归都从start开始，不往回走。
    for i := start; i <= n; i++ { // 从start开始，不往回走，避免出现重复组合
        //在每一层递归中，还会进行剪枝操作。如果剩余可选数字的数量不足以凑齐剩余需要的数字个数，则不再进行递归。
        if n-i+1 < k-len(path) { // 剪枝
            break
        }
        path = append(path, i)
        dfs(n, k, i+1)
        path = path[:len(path)-1]
    }
}

func main() {
    //得到一个二维数组，其中包含了从1到4中选取2个数字的所有组合
    combine(4, 2)
}

Link

GitHub