经典题目:组合总和系列
寻找所有可行解的情况可以尝试回溯的方法
注意:树形图有两种不同的构建方法
1.根据选择当前元素选择与否构建完全二叉树。
2.利用for循环遍历所有可能的元素,构建多叉树。(根据题目要求,是否允许重复集合,决定for循环的起始位置)
产生重复的原因是:在每一个结点,做减法,展开分支的时候,由于题目中说 每一个元素可以重复使用,我们考虑了 所有的 候选数,因此出现了重复的列表。
可不可以在搜索的时候就去重呢?答案是可以的。遇到这一类相同元素不计算顺序的问题,我们在搜索的时候就需要 按某种顺序搜索。具体的做法是:每一次搜索的时候设置 下一轮搜索的起点 begin
即:从每一层的第 22 个结点开始,都不能再搜索产生同一层结点已经使用过的 candidate 里的元素。
组合总和I
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
构建方法一:根据选择当前元素与否
构建方法二:构建所有可能情况的多叉树
组合总和II
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。(解集不能有重复)
与组合总和I的区别是每个数字只能用一次,解集都不能重复
存在相同元素时,后面元素为前面元素的子集,要忽略,否则会发生解集重合