代码随想录算法训练营|day25

回溯：i宽度约束，sum深度约束

func combinationSum3(k int, n int) [][]int {
	res := [][]int{}
	path := []int{}
	var help func(startIndex, sum, k, n int)
	help = func(startIndex, sum, k, n int) {
		if len(path) == k {
			if sum == n {
                tmp := make([]int, k)
                copy(tmp, path)
				res = append(res, tmp)
			}
			return
		}
		for i := startIndex; i <= 9 - (k - len(path)) + 1; i++ {
			path = append(path, i)
			help(i + 1, sum + i, k, n)
			path = path[:len(path) - 1]
		}
	}
	help(1, 0, k, n)
	return res
}

回溯：path用来处理路径上的结果参数；递归函数用来寻找可能符合要求的路径 ；回溯是为了保证路线之间的独立性

func letterCombinations(digits string) []string {
	res := []string{}
	 if len(digits) == 0 {
        return res
    }

	var path []byte
	phoneMap := map[string]string{
		"2": "abc",
		"3": "def",
		"4": "ghi",
		"5": "jkl",
		"6": "mno",
		"7": "pqrs",
		"8": "tuv",
		"9": "wxyz",
	}
	var help func(index int, digits string)
	help = func(index int, digits string) {
		if len(path) == len(digits) {
			res = append(res, string(path))
			return
		}
		num := string(digits[index])
		if chars, ok := phoneMap[num]; ok {
			for i := 0; i < len(chars); i++ {
				path = append(path, []byte(chars)[i])
				help(index+1, digits)
				path = path[:len(path)-1]
			}
		}

	}
	help(0, digits)
	return res
}