可视化图解算法61：组合

原创

用户11589437

修改于 2025-09-18 16:28:17

170

文章被收录于专栏：数据结构与算法精讲数据结构与算法精讲

LeetCode 77. 组合

可视化图解算法61：组合

1. 题目

描述

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

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

示例 1：

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

示例 2：

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

提示：

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

2. 解题思路

对于组合问题，可以通过回溯算法完成。

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

3. 编码实现

核心代码如下：

var (
  result [][]int //结果集
  path   []int   //路径
)

func combine(n int, k int) [][]int {
  result = make([][]int, 0)
  path = make([]int, 0)
  backtracking(n, k, 1)
  return result
}
func backtracking(n int, k int, start int) {
  // 2.递归终止条件：分枝进入结尾，找到一种组合（ k 减到了 0，说明找到了一个有效的组合）
  if k == 0 {
    //2.1 存放结果
    tmp := make([]int, len(path))
    copy(tmp, path)
    result = append(result, tmp)
    //2.2 返回
    return
  }
  //1.选择：在本层集合中遍历元素
  for i := start; i <= n; i++ {
    //1.1 处理节点（ 将当前数字添加到路径中）
    path = append(path, i)
    // 1.2 递归（递归调用，注意下一个组合从 i+1 开始，因为组合中的数字是不重复的）
    backtracking(n, k-1, i+1)
    //1.3 回溯，撤销选择（移除当前数字，以便尝试其他组合）
    path = path[:len(path)-1]
  }
}

具体完整代码你可以参考下面视频的详细讲解。