子集型回溯

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]
}
}

组合型回溯

排列型回溯