216.组合总和III
文章：4. 组合总和III
题目：216. 组合总和 III
【思路】
二编：把i写成了startIndex
和77.组合相似的解法。
在写题目的过程中，经常把回溯函数的遍历起始索引写成startIndex，而我们需要写的是i。
startIndex是在同一个集合里面遍历，防止重复遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
List<List<Integer>>res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backtracking(k,n,1,0);
return res;
}
public void backtracking(int k,int n,int startIndex,int sum ){
if(sum > n)return ;
if(path.size() == k){
if(sum == n)
res.add(new ArrayList<>(path));
return;
}
for(int i = startIndex;i<=9-(k-path.size())+1;i++){
sum+=i;
path.add(i);
backtracking(k,n,i+1,sum);
sum-=i;
path.removeLast();
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func combinationSum3(k int, n int) [][]int {
res := [][]int{}
path := []int{}
var dfs func(k,n,startIndex,sum int )
dfs = func(k,n,startIndex ,sum int){
if len(path) == k{
if sum == n{
item := make([]int,len(path))
copy(item,path)
res = append(res,item)
}
return
}
for i:=startIndex ;i<=9 ;i++{
path = append(path,i)
dfs(k,n,i+1,sum+i)
path = path[:len(path)-1]
}
}
dfs(k,n,1,0)
return res
}
|
17.电话号码的字母组合
文章：5. 电话号码的字母组合
题目：17. 电话号码的字母组合
【思路】
二编：忘记了string是由byte组成的。
本题是通过回溯一层层的构建每一层需要递归的数组（在map取）
回溯算法要提前确定好树的宽度和深度。
回溯三部曲：
需要一个字符串s来收集叶子节点的结果，然后用一个字符串数组result保存起来，定义为全局变量。
参数：需要题目所给的字符串、以及用来记录遍历到第几个数字的index
如果index等于输入的数字个数，然后收集结果，结束本层递归。
取index指向的数字，并找到对应的字符集（手机键盘的字符集），然后使用for循环来处理这个字符集。
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
| class Solution {
List<String>list = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if(digits == null || digits.length() ==0 ){
return list;
}
String[] numString ={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"} ;
backtracking(digits,numString,0);
return list;
}
StringBuilder temp = new StringBuilder();
public void backtracking(String digits,String[] numString,int num){
if(num == digits.length()){
list.add(temp.toString());
return ;
}
String str = numString[digits.charAt(num)-'0'];
for(int i = 0 ; i < str.length();i++){
temp.append(str.charAt(i));
backtracking(digits,numString,num+1);
temp.deleteCharAt(temp.length()-1);
}
}
}
|
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
| var(
m []string
path []byte
res []string
)
func letterCombinations(digits string) []string {
m = []string{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}
path,res = make([]byte,0),make([]string,0)
if digits == ""{
return res
}
dfs(digits,0)
return res
}
func dfs(digits string,start int){
if len(path) == len(digits){
tmp := string(path)
res = append(res,tmp)
return
}
digit := int(digits[start]-'0')
str := m[digit-2]
for j:=0;j<len(str);j++{
path = append(path,str[j])
dfs(digits,start+1)
path = path[:len(path)-1]
}
}
|
【算法总结】
- 组合总数III：规定了数组的数为1-9，递归即可，使用下标加入递归函数，下标需要+1防止出现重复的数
- 电话号码的字母组合：使用map存，通过每一次递归构建数字对应的字母序列
