刷题笔记day27-回溯算法2

216. 组合总和 III

这个思路还是，三部曲：

• 终止条件
• 处理单层节点
• 回溯节点

题中说的是，1到9的数，不能有重复。
k个数，和为n。
那么只要 len(path) == k 的时候，判断 n 为0，就可以入切片了。

func combinationSum3(k int, n int) [][]int {path = []int{}result = [][]int{}// tmpPath = make([]int, k)nfs(k, n, 1)return result
}var path []int
var tmpPath []int
var result [][]int
func nfs(k, n, startIndex int) bool {// 终止条件if (len(path) == k ) {if n == 0 {var tmpPath = make([]int, k)copy(tmpPath, path)result = append(result, tmpPath)}return true}// 广度遍历for i := startIndex; i <= 9; i++ {// 处理单个节点path = append(path, i)// 递归nfs(k, n-i, i+1)// 回溯if (len(path) > 0) {path = path[:len(path)-1]}}return true
}

17. 电话号码的字母组合

这个思路就是在，每一个startIndex，都是一个key，然后在横向遍历字符串
终止条件是，startIndex > maxIndex。此时就是每一个数字都遍历到了

var table = map[byte]string {'2': "abc",'3': "def",'4': "ghi",'5': "jkl",'6': "mno",'7': "qprs",'8': "tuv",'9': "wxyz",
}var digit string
var path []string
var result []stringfunc letterCombinations(digits string) []string {// 这个思路还是组合的问题if digits == "" {return []string{}}digit = digitspath = []string{}result = []string{}nfs(0, len(digits)-1)return result
}func nfs(currIndex, maxIndex int) bool {// 终止条件if currIndex > maxIndex {var tmp stringfor _, x := range path {tmp += x}result = append(result, tmp)return true}var key = digit[currIndex]var data = table[key]for i := 0; i < len(data); i++ {// 单个节点path = append(path, string(data[i]))nfs(currIndex+1, maxIndex)// 回溯if (len(path) > 0) {path = path[:len(path)-1]}}return true
}