回溯+剪枝

经典题目:组合总和系列

寻找所有可行解的情况可以尝试回溯的方法


注意:树形图有两种不同的构建方法

1.根据选择当前元素选择与否构建完全二叉树。

2.利用for循环遍历所有可能的元素,构建多叉树。(根据题目要求,是否允许重复集合,决定for循环的起始位置)

产生重复的原因是:在每一个结点,做减法,展开分支的时候,由于题目中说 每一个元素可以重复使用,我们考虑了 所有的 候选数,因此出现了重复的列表。

可不可以在搜索的时候就去重呢?答案是可以的。遇到这一类相同元素不计算顺序的问题,我们在搜索的时候就需要 按某种顺序搜索。具体的做法是:每一次搜索的时候设置 下一轮搜索的起点 begin

即:从每一层的第 22 个结点开始,都不能再搜索产生同一层结点已经使用过的 candidate 里的元素。


组合总和I

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

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


构建方法一:根据选择当前元素与否


构建方法二:构建所有可能情况的多叉树



组合总和II

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

candidates 中的每个数字在每个组合中只能使用一次。(解集不能有重复)

与组合总和I的区别是每个数字只能用一次,解集都不能重复


存在相同元素时,后面元素为前面元素的子集,要忽略,否则会发生解集重合

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。