LC-77-组合

组合

LeetCode题目链接：77. 组合 - 力扣（LeetCode）

难度：中等

分析

本题属于典型的递归回溯的题型，遍历给定数组，递归回溯组合出所有可能的组合即可

注意：组合需要进行去重（组成元素相同但是顺序不同仍然属于同种组合）

思路

1. 遍历数组，加入临时结果集（注意去重的判断逻辑）
2. 递归遍历数组
3. 临时结果集回溯后继续遍历

递归结束条件：当临时结果集中的元素个数符合条件时即遍历结束，加入最终结果集并退出递归

点我展开

GolangJava

func recurve(idx int, n int, k int, cur *[]int, res *[][]int) {
	if len(*cur) == k {
		tmp := make([]int, len(*cur))
		copy(tmp, *cur)
		*res = append(*res, tmp)
		return
	}
	for i := idx + 1; i <= n; i++ {
		*cur = append(*cur, i)
		recurve(i, n, k, cur, res)
		*cur = (*cur)[:len(*cur)-1]
	}
}

func Combine(n int, k int) [][]int {
	res := make([][]int, 0)
	cur := make([]int, 0, k)
	recurve(0, n, k, &cur, &res)
	return res
}

提交

参考资料

代码随想录