算法训练营day21,回溯1
77. 组合
func combine(n int, k int) [][]int {
//存储全部集合
result := make([][]int, 0)
//存储单次集合
path := make([]int, 0)
var backtrace func(n int, k int, startIndex int)
backtrace = func(n int, k int, startIndex int) {
//当单次集合大小和k值相等，找到本次集合，但path需要一直使用需要用temp临时存储然后赋给result
if len(path) == k {
temp := make([]int, k)
copy(temp, path)
result = append(result, temp)
return
}
for i := startIndex; i <= n; i++ {
if n-i+1 < k-len(path) { // 剪枝
break
}
path = append(path, i)
backtrace(n, k, i+1)
//回溯处理
path = path[:len(path)-1]
}
}
backtrace(n, k, 1)
return result
}