LeetCode 39. Combination Sum(组合总
2018-08-24 本文已影响266人
烛火的咆哮
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 :
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
思路:
- 典型的深度优先遍历所有可能解的问题,由于没有设置解集的大小且所有数字都可以重复选取,必须采用能够自动挖掘解集的解法
- 通过递归的方式对所有可能解集进行遍历
- 使用
Arrays.sort(candidates);先对数组进行排序,依然是该类题目提高效率和增加解法的方式 - 由于采用递归,需要优化递归方法的每一行代码,防止出现无限循环,无效或低效代码等问题
代码:
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int len = candidates.length;
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
if (len == 0)
return res;
//先排个序
Arrays.sort(candidates);
combinationSumHelp(res, list, candidates, target, 0);
return res;
}
private boolean combinationSumHelp(List<List<Integer>> res, List<Integer> list, int[] candidates, int target,
int start) {
// 对减去后的target值进行判断,
if (target < 0)
return false;
else if (target == 0) {
// list对象一直处于变动中,不能直接导入list对象,
List<Integer> temp = new ArrayList<>(list);
res.add(temp);
return false;
} else {
for (int i = start; i < candidates.length; i++) {
list.add(candidates[i]);
//深度优先遍历,就像一只深入地底的探测器
boolean flag = combinationSumHelp(res, list, candidates, target - candidates[i], i);
list.remove(list.size() - 1);
//此路不通时,由于排序后的数组,i之后数字只能更大,跳出循环
if (!flag)
break;
}
}
return true;
}
分析:
- 使用
Arrays.sort(candidates);先排序 - 参数
target在list每加入一个数字元素时,值减少,通过对target的判断,选择操作种类 - 深度优先遍历,当
target始终大于0时,会一直进行搜索,不断跳入新的递归方法,直到target小于等于0或数组到达尾部 - 当搜索到达尾部时,通过不断去除
list最后元素,for循环进入到下一个 i 的深度遍历,来达到全部组合的遍历 -
flag用于跳出循环,增加效率,排序后的数组呈升序,当返回此路不通时,for循环后面更大的数也将返回false,可以直接跳出
总结
- 递归方法总是需要大量优化,递归的位置也尤为重要
- 深度优先遍历,其实就是获取所有解的过程,在其中分辨需要的解进行操作
- 对于可变对象的操作需要谨慎,为其重新分配空间可以使其变为不可变对象(没有被增删改)
- 尽量不使用集合来处理问题是数组类题目提升效率的基本操作
