代码随想录算法训练营第25天 | 216.组合总和III、17.电话号码的字母组合

本文主要是介绍代码随想录算法训练营第25天 | 216.组合总和III、17.电话号码的字母组合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接: 216.组合总和III
链接: 17.电话号码的字母组合

自己看到题目的第一想法

216.组合总和III：递归函数终止条件为搜索得到的数相加为n，其他逻辑和组合一样。
17.电话号码的字母组合：先把各个字母对应数字的映射关系存一下，针对读取数字对应字母，采用回溯来解决。具体细节是真的不太清楚。

看完代码随想录之后的想法

216.组合总和III：通过这道题，并不知道组合个数的情况下也更能看出回溯算法相对于for循环的优势。要注意的点就是：在画树形图的时候，剩余集合的范围是什么？理解完树形图之后再看代码。
这里贴上卡哥网站的树形图：

再贴上卡哥总结的回溯算法模板：

void backtracking(参数）{if(终止条件){存放结果；return;}for(选择：本层集合中元素（树中结点孩子的数量就是集合的大小）){处理节点；backtracking(路径，选择列表);//递归回溯，撤销处理结果；}}

结合三部曲去一步步填充内容（1）参数和返回值 （2）结束条件：根据k来控制树形图的深度，如果树形图的深度达到了题目要求的集合数量，就判断是否此时路径和为题目要求的n，如果满足题目要求就将结果添加入结果集里。所以此时也可以看出需要声明全局变量path用于存储路径元素，result用于存储结果集。（3）处理逻辑：首先是for循环里的集合元素集，要确定起始点，和结束点，处理节点部分就是路径更新和求和，之后在进行逆操作。
针对减枝操作，有两点，一方面是当求和已经大于目标和的时候就可以直接返回了，可以直接在终止条件中进行；另一方面是集合数量要在满足题意的范围内，可以在for循环中对集合元素的终止点进行限定。
17.电话号码的字母组合：
这道题和前面的组合题目不一样的地方就是，前面的组合题目是在一个集合里，而这道题在不同集合里取元素的组合。
注意的点：画树形图要明白树的宽度和深度是由什么控制的。

这篇关于代码随想录算法训练营第25天 | 216.组合总和III、17.电话号码的字母组合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---