题目：216. 组合总和 III
思路：
多加一个记录和的参数，还有一个起始位置的参数(不重复就得加)
结束条件是个数到了k：
- 如果此时sum == n那就说明答案正确
- 如果此时sum != n那就直接返回
剪枝的话：
如果之后的和大于n那就没必要继续遍历了
代码：
var res [][]int // 答案
var path []int // 路径
func combinationSum3(k int, n int) [][]int {
res = make([][]int, 0)
path = make([]int, 0, k)
CombinationSum3(k,n,0,1)
return res
}
func CombinationSum3(k,n,sum,start int) {
if len(path) == k { // 结束条件：长度等于k
if sum == n { // 添加条件：sum == n
res = append(res, append([]int{}, path...))
}
return
}
for i := start; i <= 9; i++ { // 因为不能重复所以要有起始位置
if sum + i > n { // 剪枝
break
}
path = append(path, i) // 添加
CombinationSum3(k, n, sum + i,i+1) // 下一个循环
path = path[:len(path)-1] // 取消
}
return
}
参考：
题目：17. 电话号码的字母组合
思路：
思路和上面一样，就是多写了一个map做键位的映射。
代码：
var maps = map[byte]string{ // 做一个映射关系
'2' : "abc",
'3' : "def",
'4' : "ghi",
'5' : "jkl",
'6' : "mno",
'7' : "pqrs",
'8' : "tuv",
'9' : "wxyz",
}
var res []string // 答案
var path []byte // 路径
func letterCombinations(digits string) []string {
if digits == "" { // 空直接返回空
return []string{}
}
res = make([]string, 0)
path = make([]byte, 0,len(digits))
LetterCombinations(digits)
return res
}
func LetterCombinations(digits string) {
if len(digits) == 0 { // 结束/添加条件：digital内没有元素
res = append(res, string(path))
return
}
for _, ch := range maps[digits[0]] { // 遍历映射关系
path = append(path, byte(ch)) // 添加
LetterCombinations(digits[1:]) // 下一个循环
path = path[:len(path)-1] // 取消
}
return
}