77-组合.md

77. 组合

leecode原题

题目

给定两个整数 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

解题思路

思路

参考代码思考录

回溯法解决的问题都可以抽象为树形结构（N叉树），用树形结构来理解回溯就容易多了。

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

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

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

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

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

那么如何在这个树上遍历，然后收集到我们要的结果集呢？

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

实现

源码

var (
	path = make([]int, 0)   // 迭代的路径记录
	res  = make([][]int, 0) // 最终结果记录
)

func backtracking(n int, k int, startIndex int) {
	if len(path) == k {
		// 这里拷贝一定一定要当心!!!!!!
		temp := make([]int, k)
		copy(temp, path)
		res = append(res, temp)
		return
	}
	// for i := startIndex; i <= n; i++ { // 未裁枝
	for i := startIndex; i <= n-(k-len(path))+1; i++ { // 控制树的横向遍历
		path = append(path, i)    // 处理节点
		backtracking(n, k, i+1)   // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
		path = path[:len(path)-1] // 回溯，撤销处理的节点
	}
}

func combine(n int, k int) [][]int {
	path = make([]int, 0)
	res = make([][]int, 0)
	backtracking(n, k, 1)
	return res
}