📑 题目：77. 组合

🚀 本题 LeetCode 传送门

题目大意

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

解题思路

• 计算排列组合中的组合，用 DFS 深搜即可，注意剪枝

代码

package leetcode
func combine(n int, k int) [][]int {
 if n <= 0 || k <= 0 || k > n {
  return [][]int{}
 }
 c, res := []int{}, [][]int{}
 generateCombinations(n, k, 1, c, &res)
 return res
}
func generateCombinations(n, k, start int, c []int, res *[][]int) {
 if len(c) == k {
  b := make([]int, len(c))
  copy(b, c)
  *res = append(*res, b)
  return
 }
 // i will at most be n - (k - c.size()) + 1
 for i := start; i <= n-(k-len(c))+1; i++ {
  c = append(c, i)
  generateCombinations(n, k, i+1, c, res)
  c = c[:len(c)-1]
 }
 return
}