216.组合总和III
文章：4. 组合总和III
题目：216. 组合总和 III
【思路】
和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
| func combinationSum3(k int, n int) [][]int {
res := make([][]int,0)
path :=make([]int,0,k)
var backtracking func(k,n,sum,startIndex int)
backtracking = func(k,n,sum,startIndex 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;i++{
path = append(path,i)
backtracking(k,n,sum+i,i+1)
path = path[:len(path)-1]
}
}
backtracking(k,n,0,1)
return res
}
|
17.电话号码的字母组合
文章：5. 电话号码的字母组合
题目：17. 电话号码的字母组合
【思路】
回溯算法要提前确定好树的宽度和深度。
回溯三部曲：
需要一个字符串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]
}
}
|
【算法总结】
