代码随想录 | Day29 | 回溯算法：电话号码的字母组合&&组合总和

主要学习内容：

组合题目的模板

17.电话号码的字母组合

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

解法思路：

这道题其实主要的难点是要搞清楚模板里面的for循环到底在干些什么事情

20201123200304469树的每个分支其实就是每一次for循环产生的，每一层递归函数的for循环可以整整产生一层节点，比如第一层递归函数的for产生的就是要分别取a，b，c，一共循环三次，取出来三个数，所以第一层有三个节点

第二层也是类似，分别选了def，才有了ad，ae，af三个结果，所以有3*3=9个结果

而第一层的abc是数字2的集合，第二层的def是数字3的集合，所以每一层递归函数都是在遍历一个不同的数的集合，我们要做的就是让递归函数知道他这一层要遍历哪个数字的集合

1.函数参数和返回值

1
2
3
vector<string> res;
vector<string> s{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//0,1没有，从2开始对应
void backtracking(string str,string digits,int index)

res存放结果集，s存放数字对应的字符串

传入的参数，str相当于path，收集我们已经知道的答案

digits是题目中给的字符串，index传递本层递归函数要遍历哪个集合

2.终止条件

一个数字只选一个字母，所以只要我们收集的和题目给的字符串一样大，就是答案了

1
2
3
4
5
if(str.size()==digits.size())
{
	res.push_back(str);
	return;
}

3.本层代码逻辑

t表示的是我们这层递归函数选的哪个数字，是由字符串里面的数字转换过来的

s[t]对应我们选的字符串（abc还是def）

遍历自然就遍历我们选的这个字符串，从0遍历到它结束，因为它的每一个字符我们都得选一遍的

s[t][i]就是对应每个字母，我们压入字符串（这里就是把23这个例子的a压入了），然后进入下一层递归去选下一个字母（去选def里面的字母去了就）

递归的index就直接+1即可，因为我们要选的就是下一个数字对应的集合

递归结束，把刚刚压入的字母弹出（把a弹出，等i等于1压入b）

1
2
3
4
5
6
7
8
int t=(int)(digits[index]-'0');
for(int i=0;i<s[t].size();i++)
{
	str.push_back(s[t][i]);
	backtracking(str,digits,index+1);
    //回溯
    str.pop_back();
}

完整代码：

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
class Solution {
public:
    vector<string> res;
    vector<string> s{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    void backtracking(string str,string digits,int index)
    {
        if(str.size()==digits.size())
        {
            res.push_back(str);
            return;
        }
        int t=(int)(digits[index]-'0');
        for(int i=0;i<s[t].size();i++)
        {
            str.push_back(s[t][i]);
            backtracking(str,digits,index+1);
            str.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0)
            return res;
        string str;
        backtracking(str,digits,0);
        return res;
    }
};

注：digits如果为空传个空就是。

39.组合总和

39. 组合总和 - 力扣（LeetCode）

思路：

和之前的思路差不多组合总和III，就是之前每层遍历是从i+1开始，是为了防止出现重复的数字，现在遍历从i开始，因为本身的数可以重复取

1.函数返回值和参数

1
2
vector<vector<int>> res;
void backtracking(vector<int> path,int sum,int index,vector<int> candidates,int target)

res记录结果

path收集当前组合

sum当前集合的总和

index从哪个数开始

candidates题目给的数组

target题目给的目标值

2.终止条件

当前总和已经大于target了，没必要再递归了

如果大小等于target，收集结果

1
2
3
4
5
6
7
if(sum>target)
	return;
if(sum==target)
{
	res.push_back(path);
	return;
}

3.本层逻辑

额就是可以重复取当前数字，所以下一层递归函数传参传i而不是i+1，i+1可以避免取重复的数字

不太好理解的话大家可以画个图模拟一下

1
2
3
4
5
6
for(int i=index;i<candidates.size();i++)
{
	path.push_back(candidates[i]);
	backtracking(path,sum+candidates[i],i,candidates,target);
	path.pop_back();
}

完整代码：

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 {
public:
    vector<vector<int>> res;
    void backtracking(vector<int> path,int sum,int index,vector<int> candidates,int target)
    {
        if(sum>target)
            return;
        if(sum==target)
        {
            res.push_back(path);
            return;
        }
        for(int i=index;i<candidates.size();i++)
        {
            path.push_back(candidates[i]);
            backtracking(path,sum+candidates[i],i,candidates,target);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> path;
        backtracking(path,0,0,candidates,target);
        return res;
    }
};