77. 组合

mid

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

DFS 回溯

n 中选 k 个，经典的组合问题

注意用 startIndex 避免重复

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func combine(n int, k int) [][]int {
	res := make([][]int, 0)
	set := make([]int, 0)
	var dfs func(startIndex, layer int)
	dfs = func(startIndex, layer int) {
		if layer == k {
			res = append(res, append([]int{}, set...))
			return
		}
		for i := startIndex; i < n; i++ {
			set = append(set, i+1)
			dfs(i+1, layer+1)
			set = set[:len(set)-1]
		}
	}
	dfs(0, 0)
	return res
}

剪枝

来个剪枝，帅的一

如果当前能够提供的元素数量小于还需要的元素数量，那就剪去

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func combine(n int, k int) [][]int {
	res := make([][]int, 0)
	set := make([]int, 0)
	var dfs func(startIndex, layer int)
	dfs = func(startIndex, layer int) {
		if layer == k {
			res = append(res, append([]int{}, set...))
			return
		}
		if n-startIndex < k-len(set) {
			// 剪枝 如果当前能够提供的元素数量小于还需要的元素数量 那就剪去
			return
		}
		for i := startIndex; i < n; i++ {
			set = append(set, i+1)
			dfs(i+1, layer+1)
			set = set[:len(set)-1]
		}
	}
	dfs(0, 0)
	return res
}