代码随想录算法训练营|day24

77.组合

以n=5,k=3为例

(1)for循环遍历，递归选择符合要求的值加入path，len(path)==k时，返回
statrtIndex保证每次递归取到的值不重复
剪枝：i<=n-(k-len(path))+1 后续需要k-len(path)个值，因为i可选区间左闭右闭，故+1

func combine(n int, k int) [][]int {res := [][]int{}path := []int{}var helper func(n, k, startIndex int)helper = func(n, k, startIndex int) {if len(path) == k {tmp := make([]int, k)copy(tmp, path)res = append(res, tmp)return}for i:= startIndex; i <= n; i++ {path = append(path, i)helper(n, k, i+1)path = path[:len(path) - 1]}}helper(n, k, 1)return res
}

(2)递归枚举每个值，选/不选
若不选当前值，递归下一个值；若选当前值，加入结果集，回溯，保证当前状态不影响下一次递归

func combine(n int, k int) [][]int {res := [][]int{}path := []int{}var helper func(n, k, i int)helper = func(n, k, i int) {if len(path) == k {tmp := make([]int, k)copy(tmp, path)res = append(res, tmp)return}if i > n {return}helper(n, k, i + 1)path = append(path, i)helper(n, k, i + 1)path = path[:len(path) - 1]}helper(n, k, 1)return res
}

代码随想录文章详解

理论基础
77.组合

总结

循环嵌入递归，循序渐进。感谢代码随想录训练营。