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
}