组合枚举（回溯算法）

递归与回溯

说明

只从后续元素继续选择以避免顺序重复；生成所有大小为 k 的组合。

分析

path 保存当前已选元素，下次只从更大的序号开始，避免把同一组元素以不同顺序重复输出。选满 k 个时复制结果，然后回溯继续搜索。

图解推演

从 1..4 选 2 个时，选择 1 后只尝试 2、3、4；不会再生成 [2,1]。选择 4 后已经没有更大候选，分支失败。剩余候选数小于 k−len(path) 时可直接返回；保存结果必须复制 path，避免后续回溯覆盖。

查看图表代码

适用前提与边界

可加入“剩余候选不足”判断，减少不可能完成的分支。

示例输入与调用

fmt.Println(Combinations(4, 2))

运行输出

[[1 2] [1 3] [1 4] [2 3] [2 4] [3 4]]

完整 Go 示例

package main

import "fmt"

func Combinations(n, k int) [][]int {
	out := [][]int{}
	path := []int{}
	var dfs func(int)
	dfs = func(start int) {
		if len(path) == k {
			out = append(out, append([]int(nil), path...))
			return
		}
		for x := start; x <= n; x++ {
			path = append(path, x)
			dfs(x + 1)
			path = path[:len(path)-1]
		}
	}
	dfs(1)
	return out
}

func main() {
	fmt.Println(Combinations(4, 2))
}