216.组合总和III

• 回溯

var temp = []int{}
var res = [][]int{}
var mp = make([]bool, 10)
func sumTarget(target int) bool{
    sum := 0
    for i := 0; i < len(temp); i++ {
        sum += temp[i]
    }
    return target == sum
}
func dfs (k, n, startIndex int) {
    if k == 0 {
        if !sumTarget(n) {
            return
        }
        cp := make([]int, len(temp))
        copy(cp, temp)
        res = append(res, cp)
        return 
    }
    for i := startIndex; i <= 9; i++ {
        if mp[i] {
            continue
        }
        temp = append(temp, i)
        mp[i] = true
        dfs(k-1, n, i+1)
        mp[i] = false
        temp = temp[:len(temp)-1]
    }
}
func combinationSum3(k int, n int) [][]int {
    temp = []int{}
    res = [][]int{}
    dfs(k, n, 1)
    return res
}

17.电话号码的字母组合

var numMap = make(map[int][]byte)
var temp []byte
var res []string

func initNumMap() {
    temp = []byte{}
    res = []string{}
    offset := 0
    for i := 2; i <= 9; i++ {
        numMap[i] = []byte{}
        for j := 0; j < 3; j++ {
            c := byte('a' + offset)
            numMap[i] = append(numMap[i], c)
            offset++
        }
        if i == 7 || i == 9 {
            c := byte('a' + offset)
            numMap[i] = append(numMap[i], c)
            offset++
        }
    }
}

func dfsBack(digits string, index int) {
    if index == len(digits) {
        str := string(temp[:])
        if str != "" {
            res = append(res, str)
        }
        return
    }
    num := int(digits[index] - '0')
    chars := numMap[num]
    for _, c := range chars {
        temp = append(temp, c)
        dfsBack(digits, index+1)
        temp = temp[0 : len(temp)-1]
    }
}
func letterCombinations(digits string) []string {
    initNumMap()

    dfsBack(digits, 0)
    return res
}

---

• 分类： 算法
• 标签： 算法基础 回溯