77 组合

题目描述#

给定两个整数 n 和 k，要求从范围 [1, n] 中选出所有可能的 k 个数的组合。答案可以按任意顺序返回。

组合只关心选了哪些数，不关心选择顺序，所以 [1, 2] 和 [2, 1] 属于同一种组合。

思路#

这题也是标准回溯题，不过重点不是“能不能选”，而是“怎样避免重复组合”。嘿嘿，如果把每个数字都当成一张照片，那组合题要做的就是挑出 k 张放进相册，但同一组照片换个摆放顺序可不能算新相册哦～

这份代码采用倒序枚举。dfs(i) 表示接下来只能从 1 到 i 这些数字里继续选择，当前已经选好的数字保存在 path 里。每次枚举一个数字 j 放进 path，下一层递归就只能继续从 1 到 j-1 中选择，这样可以保证每个组合只出现一次。

变量 d := k - len(path) 表示还需要选择多少个数。如果 d == 0，说明当前组合已经凑够 k 个数，就把 path 复制一份加入答案。这里必须复制，不能直接把 path 放进去，因为后续回溯会继续修改同一个底层数组；本姑娘可不想刚拍好的照片被后面的动作悄悄覆盖掉嘛。

循环条件 j >= d 是剪枝。因为当前选了 j 以后，下一层只能从更小的数里继续选，如果 j 太小，剩下的数字数量就不够凑满 d 个了。这个剪枝能减少无意义递归，让搜索过程更利落。时间复杂度主要由答案数量决定，为 O(k * C(n, k))；额外空间复杂度为 O(k)，不计返回结果。

思维边界#

组合去重：通过限制下一层只能选择更小的数，避免同一组数字以不同顺序重复出现。
倒序枚举：dfs(i) 表示只能在 [1, i] 中继续选，递归到 dfs(j-1) 后搜索范围自然缩小。
剪枝条件：j >= d 保证当前可选数字数量足够，不够凑满组合时不再递归。
路径复制：加入答案时需要使用 slices.Clone(path)，否则后续回溯会修改已保存结果。
恢复现场：递归返回后通过 path = path[:len(path)-1] 撤销本层选择。

代码#

import "slices"

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

	// 枚举选哪个：在 1 到 i 中选一个数，加到 path 末尾
	var dfs func(int)
	dfs = func(i int) {
		d := k - len(path) // 还要选 d 个数
		if d == 0 {        // 选好了
			ans = append(ans, slices.Clone(path))
			return
		}

		// 枚举的数不能太小，否则后面没有数可以选
		for j := i; j >= d; j-- {
			path = append(path, j)
			dfs(j - 1)
			path = path[:len(path)-1] // 恢复现场
		}
	}

	dfs(n) // 从 n 开始倒着枚举
	return
}