子集型回溯

17. 电话号码的字母组合 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var (
    m []string
    path []byte
    res []string
)

func letterCombinations(digits string) []string {
	// 将index 和 字符串对应起来
	m = []string{"","","abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
	path, res = make([]byte,0),make([]string,0)
    if digits == "" {
        return res
    }
	backTracking(digits,0)
	return res
}
func backTracking(digits string, start int) {
	// 终止条件 ，遍历完digits
	if start == len(digits) {
        tmp := string(path)
		res = append(res,tmp)
		return
	}
	// 找到 digit
	digitNum := int(digits[start] - '0')
	// 遍历 digit 对应的map 字符串
	str := m[digitNum]
	for i:=0;i< len(str);i++ { // i 从0开始，因为每个字典都是一个独立的集合，之前的组合是一个集合，所以才从start 开始
		path = append(path,str[i])
		backTracking(digits,start+1)
		path =path[:len(path)-1]
	}
}

组合型回溯

排列型回溯