【代码随想录】算法训练计划25

1、216. 组合总和 III

题目：
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字最多使用一次
返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

思路：

也是很经典的回溯

func combinationSum3(k int, n int) [][]int {
    list := make([]int, 0)
    res := make([][]int, 0)
    backtrack(&res, list,k,n,1)
    return res
}
func backtrack(res *[][]int, list []int,k,n,index int) {
    if len(list) == k {
        sum := 0
        for _,v := range list {
            sum += v
        }
        if sum == n {
            ans := make([]int, len(list))
            copy(ans, list)
            *res = append(*res, ans)
        }
        return //剪枝，没必要在这里继续从这个位置回溯了
    }
    for i:=index; i<=9; i++ {
        list = append(list, i)
        backtrack(res, list, k,n,i+1)
        list = list[:len(list)-1]
    }
}

2、17. 电话号码的字母组合

题目：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

思路：

意遍历时候，是index+1，而不是i+1，因为index代表的是第几个map，是遍历列表变了

func letterCombinations(digits string) []string {
    if len(digits) == 0 {return nil}
    digitsMap := [10]string {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",
    }
    res := make([]string, 0)
    list := ""
    backtrack(&res, list,digits,0,digitsMap)
    return res
}
func backtrack(res *[]string,list,digits string, index int, digitsMap [10]string) {
    if len(list) == len(digits) {
        *res = append(*res, list)
        return
    }
    // 拿到digit代表的数字
    listK := digits[index] - '0'
    // 拿到对应的map集合
    dm := digitsMap[listK]
    for i:=0; i<len(dm); i++ {
        list = list+string(dm[i])
        backtrack(res, list, digits, index+1,digitsMap)
        list = list[:len(list)-1]
    }
}