LeetCode 77. 组合

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 77. 组合

思路分析

回溯问题

参考代码

func combine(n int, k int) [][]int {
	var res [][]int
	var cur []int

	var dfs func(start int)
	dfs = func(start int) {
		// 如果组合长度等于 k，加入结果集
		if len(cur) == k {
			res = append(res, append([]int(nil), cur...))
			return
		}

		// 从 start 开始尝试每个数字
		for i := start; i <= n; i++ {
			// 剪枝：如果剩下的数字不足以构成长度 k，提前退出
			if n-i+1 < k-len(cur) {
				break
			}

			// 选择当前数字
			cur = append(cur, i)
			// 递归进入下一层，i+1 避免重复使用
			dfs(i + 1)
			// 回溯，移除最后一个数字
			cur = cur[:len(cur)-1]
		}
	}

	dfs(1)
	return res
}

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/67920981