组合

怎样从“n=4,k=2,返回所有 2 数组合。”推导出 回溯 · 组合，并证明每次状态变化都不会漏掉答案？

中心结论：回溯 start:选则加入 path,到 k 收集;同 LC78 子集但 depth 固定 k。

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

在本站主例中，n=4,k=2,返回所有 2 数组合。

算法最终需要得到或观察：[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]。

先生成全部结果再过滤会探索大量无效分支；回溯在选择阶段剪枝，并在返回时恢复现场。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“选择树与撤销绳”，明确答案需要观察什么。
2. 2状态只维护 path 深度、start。
3. 3转移每一步按照 回溯 start:选则加入 path,到 k 收集;同 LC78 子集但 depth 固定 k。
4. 4收尾读取 [1,2],[1,3],[1,4],[2,3],[2,4],[3,4]。，并复核边界与复杂度。

路径记录已做选择，候选集合决定下一步，撤销保证兄弟分支互不污染。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：path 深度、start。

计算排列组合中的组合，用 DFS 深搜即可，注意剪枝

回溯 start:选则加入 path,到 k 收集;同 LC78 子集但 depth 固定 k。

执行过程中持续维护：path 深度、start。

正确性依赖以下不变量：path 严格递增,保证组合不重复。

面试时可以压缩为：回溯枚举 k 组合:path 存已选,start 规定只能向后选,选 i 后递归 i+1 保证递增去重,len(path)==k 时 copy 进 ans,剪枝上界 n-need+1,时间 O(C(n,k)×k) 辅助 O(k)。

落到当前题，执行机制可以压缩为：回溯 start:选则加入 path,到 k 收集;同 LC78 子集但 depth 固定 k。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入n=4,k=2,返回所有 2 数组合。 因为：回溯 start:选则加入 path,到 k 收集;同 LC78 子集但 depth 固定 k。
2. 2选 1,还需 1 个做选择。 因为：剪枝:剩余不够则跳过。
3. 3预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
4. 4选 3,还需 0 个做选择。 因为：剪枝:剩余不够则跳过。
5. 5选 4,还需 0 个做选择。 因为：剪枝:剩余不够则跳过。
6. 6选 2,还需 1 个做选择。 因为：剪枝:剩余不够则跳过。
7. 7组合 [2,3]收集合法组合。 因为：长度恰为 k。
8. 8收尾与复杂度[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]。 因为：时间 O(C(n,k) × k) · 空间 O(k) 辅助；含输出 O(C(n,k) × k)。回溯 start:选则加入 path,到 k 收集;同 LC78 子集但 depth 固定 k。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func combine(n int, k int) [][]int {
	if n <= 0 || k <= 0 || k > n {
		return [][]int{}
	}
	c, res := []int{}, [][]int{}
	generateCombinations(n, k, 1, c, &res)
	return res
}

func generateCombinations(n, k, start int, c []int, res *[][]int) {
	if len(c) == k {
		b := make([]int, len(c))
		copy(b, c)
		*res = append(*res, b)
		return
	}
	// i will at most be n - (k - c.size()) + 1
	for i := start; i <= n-(k-len(c))+1; i++ {
		c = append(c, i)
		generateCombinations(n, k, i+1, c, res)
		c = c[:len(c)-1]
	}
	return
}

func main() {
    // 1. 主例
    //    输入：mode="combinations", n=4, k=2
    //    期望：[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]。
    //
    // 2. 失败 / 未命中
    //    检查：用排列会重复 [1,2] 与 [2,1]。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC78 子集；LC46 排列
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意n=4,k=2,返回所有 2 数组合。
2. 2重复先生成全部结果再过滤会探索大量无效分支；回溯在选择阶段剪枝，并在返回时恢复现场。
3. 3优化回溯 start:选则加入 path,到 k 收集;同 LC78 子集但 depth 固定 k。
4. 4证明path 严格递增,保证组合不重复。
5. 5复杂度时间 O(C(n,k) × k)，空间 O(k) 辅助；含输出 O(C(n,k) × k)