算法训练营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

}