第二十三天 | 39. 组合总和 40.组合总和II 131.分割回文串

39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

思路:求组合(不同顺序视为同一个组合),那我们返回非递减序列就保证了组合不重复。backtrack(index, path),for循环范围for i in range(index, n),传入下一层回溯函数 backtrack(i, path),这样就可以重复使用某个元素。

40.组合总和II

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

思路:难点在于数组中的数字不唯一。如果出现[2, 3, 3] 如何保证每个3只被使用一次。解决方案:选了第一个3的枝条后,第二个3的枝条就略过。

131.分割回文串

给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。返回 s 所有可能的分割方案。

思路:1. 先定义一个回文的判断函数。2. 给一个指针随机在s中切下一段,如果是回文,加入路径,然后剩下的部分传入回溯函数。

以下是卡哥资料

 39. 组合总和 

本题是 集合里元素可以用无数次,那么和组合问题的差别 其实仅在于 startIndex上的控制

题目链接/文章讲解:https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html

视频讲解:https://www.bilibili.com/video/BV1KT4y1M7HJ 

 40.组合总和II 

本题开始涉及到一个问题了:去重。

注意题目中给我们 集合是有重复元素的,那么求出来的 组合有可能重复,但题目要求不能有重复组合。 

题目链接/文章讲解:https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html 

视频讲解:https://www.bilibili.com/video/BV12V4y1V73A

 131.分割回文串  

本题较难,大家先看视频来理解 分割问题,明天还会有一道分割问题,先打打基础。 

https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html 

视频讲解:https://www.bilibili.com/video/BV1c54y1e7k6 

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

友情链接更多精彩内容