LeetCode 中有多道组合总和(Combination Sum)的题,这些题目都是比较经典的,面试很可能会问到。我这一想,还真是。今天就来简单总结下这一系列题目,总结很重要,还要时而回顾!
Combination Sum I
第一道题的描述如下:
1 | 给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 |
注意点:
- candidates 中的数字可以无限制重复被选取。
- 解集不能包含重复的组合。
这时候头脑里很快就会产生一个思路:无限遍历该数组,直到其元素之和满足条件,然后塞入集合中。
这个想法没问题,不过在这过程中我们怎么才能满足解集不能包含重复的组合。
这个条件呢?
对对对,那就是确定一个 index,我们要保证数组不往回找就是了。
解题代码如下:
1 | public List<List<Integer>> combinationSum(int[] candidates, int target) { |
我这注释什么的都有,理解起来不成问题吧。这里需要注意的就是两个点:list.add(new ArrayList<>(tempList));
和 recursive(list, tempList, nums, remain - nums[i], i);
。
这里先对数组进行排序可以使计算更快,当然你也可以不排序。
Combination Sum II
第二道对第一道稍微加工了一下,描述如下:
1 | 给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 |
注意点:
- candidates 中的每个数字在每个组合中只能使用一次。
- 解集不能包含重复的组合。
是的,这里把条件改了,数组中的每个元素在每个组合中只能使用一次!
这就意味着每次递归操作时其下标都需要往后移一位了!
代码如下:
1 | public List<List<Integer>> combinationSum2(int[] candidates, int target) { |
相比较上一题的代码,这次只是加了一个条件判断以及递归中元素下标加了一。
这里就要对数组先进行排序操作了,新增的条件判断也是为了优化代码执行速度。
Combination Sum III
再来看第三道变形,描述如下:
1 | 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。 |
这次不给出数组了,而是规定了数组中元素的取值范围。
双手一摊,这还不是一样吗,不给我就自己造就是了!
注意点:
- 解集不能包含重复的组合。
解题代码如下:
1 | public List<List<Integer>> combinationSum3(int k, int n) { |
真不愧为机智小少年……
Combination Sum IV
第四道变形就复杂了一些了,描述如下:
1 | 给定一个由正整数组成且不存在重复数字的数组,找出和为给定目标正整数的组合的个数。 |
这里数组的元素可以重复,且组合的元素也能相同,但是顺序要不同。
一开始当然就是无脑循环了,然后满足条件就加上一,结果就是超时……
说明这么暴力不行的……
后来一想,无脑循环就相当于每一次都从头进行循环算了一遍,很多都是重复的计算。
对了,DP 浮现在了脑中,在那飘啊飘。
代码如下:
1 | private int[] dp; |
用空间换取时间的操作,DP + 递归稍微费点脑。
还有一种解法:
1 | /** |
好了,组合总和系列(Combination Sum)的题目总结完了。记住了回溯。