算法训练营day22, 回溯2

216. 组合总和 III

func combinationSum3(k int, n int) [][]int {

  //存储全部集合

  result := make([][]int, 0)

  //存储单次集合

  path := make([]int, 0)

  var backtrace func(k int, n int, sum int, startIndex int)

  backtrace = func(k int, n int, sum int, startIndex int) {

    //当单次集合大小和k值相等，找到本次集合，但path需要一直使用需要用temp临时存储然后赋给result

    if len(path) == k {

      if sum == n {

        temp := make([]int, k)

        copy(temp, path)

        result = append(result, temp)

        return

      }

    }

    for i := startIndex; i <= 9; i++ {

      if sum+i > n { // 剪枝

        break

      }

      sum += i

      path = append(path, i)

      backtrace(k, n, sum, i+1)

      //回溯处理

      sum -= i

      path = path[:len(path)-1]

    }

  }

  backtrace(k, n, 0, 1)

  return result

}

17. 电话号码的字母组合

func letterCombinations(digits string) []string {

  result := make([]string, 0)

  if len(digits) == 0 {

    return result

  }

  letterMap := make(map[int]string, 0)

  letterMap[0] = ""

  letterMap[1] = ""

  letterMap[2] = "abc"

  letterMap[3] = "def"

  letterMap[4] = "ghi"

  letterMap[5] = "jkl"

  letterMap[6] = "mno"

  letterMap[7] = "pqrs"

  letterMap[8] = "tuv"

  letterMap[9] = "wxyz"

  //存储单次集合

  path := make([]byte, 0)

  var backtrace func(digits string, index int)

  backtrace = func(digits string, index int) {

    if index == len(digits) {

      temp := string(path)

      result = append(result, temp)

      return

    }

    //转换为int

    digit := int(digits[index] - '0')

    letter := letterMap[digit]

    for i := 0; i < len(letter); i++ {

      path = append(path, letter[i])

      backtrace(digits, index+1)

      //回溯处理

      path = path[:len(path)-1]

    }

  }

  backtrace(digits, 0)

  return result

}