本文共 3457 字，大约阅读时间需要 11 分钟。
LeetCode第39题思悟——组合总和（combination-sum）
知识点预告
- 数组的排序处理；
- 分治思想的应用；
- 递归结果的返回处理；
题目要求
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。 来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为: [ [7], [2,2,3] ] 示例 2: 输入: candidates = [2,3,5], target = 8,
所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ] 来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
我的思路
涉及数组中查找，必不可少的操作是排序，接着就是二分查找；算是一种组合拳吧；根据题目描述，这道题可以采用分治的处理思路：在一组数中，寻找一些数，使它们之和等于target，那么当选定一个数时，target就会变小一点，而问题的本质却没有发生变化，这符合分治的处理手段；简单来说，就是不断选定一个数，然后将target变小，然后递归处理；
public List > combinationSum(int[] candidates, int target) { if(candidates.length==0){ return new ArrayList<>(); } Arrays.sort(candidates); return combinationSum(candidates,target,0);}private boolean contains(int[] candidates,int start,int end,int target){ int left=start,right=end; int middle; while(left<=right){ middle=(left+right)/2; if(candidates[middle] target){ right=middle-1; }else{ return true; } } return false;}private List > combinationSum(int[] candidates,int target,int start){ List > result=new ArrayList<>(); List > subResult; int index=start; int headValue=candidates[index]; int realTarget=target-candidates[index]; List item; if(contains(candidates,start,candidates.length-1,target)){ item=new ArrayList<>(); item.add(target); result.add(item); } while(headValue<=realTarget){ subResult=combinationSum(candidates,realTarget,index); if(subResult.size()!=0){ for (List answer : subResult) { answer.add(headValue); result.add(answer); } } index++; if (index
优秀解法
//解法Apublic List > combinationSum(int[] candidates, int target) { List > listAll = new ArrayList >(); List list = new ArrayList (); Arrays.sort(candidates); find(listAll,list,candidates,target,0); return listAll;}public void find(List > listAll,List tmp,int [] candidates,int target,int num){ if(target == 0){ listAll.add(tmp); return; } if(target list = new ArrayList<>(tmp); list.add(candidates[i]); find(listAll,list,candidates,target-candidates[i],i); }}//解法Bpublic List > combinationSum(int[] candidates, int target) { List > res = new ArrayList<>();//模板 Arrays.sort(candidates);//数之和就肯定要排序 不然指针没法操作 //System.out.println(candidates); backtrack(candidates, target, res, 0, new ArrayList ()); return res;}private void backtrack(int[] candidates, int target, List > res, int i, ArrayList tmp_list) { if (target < 0) return;//没啥意义 if (target == 0) { //target逐渐减小 直到0的时刻返回 res.add(new ArrayList<>(tmp_list));//加入答案并返回 和模板没有区别 return; } for (int start = i; start < candidates.length; start++) { if (target < candidates[start]) break; //System.out.println(start); tmp_list.add(candidates[start]); //System.out.println(tmp_list); backtrack(candidates, target - candidates[start], res, start, tmp_list); tmp_list.remove(tmp_list.size() - 1); //回溯与剪枝的关系？？？？ }}
差异分析
解法A和解法B在解题思路上是一致的，都是将数组的首位放到结果里，然后修改target，起到分治的效果；而我的解法里，思路一致，只是会判断一下是否存在剩余的那个数，如果存在，就算是发现了一个答案，只需要添加即可；
总结到这里，我有一点怀疑，是否二分查找有一点多余呢？毕竟优秀解法里提供的解法均没有使用到二分查找；实际上，是可以去掉的，只是去掉后，对于递归方法调用的退出条件需要再做修改，并且对结果的返回也要再做处理；而如此依赖，实际上就和优秀解法里提供的方法没什么区别了；
知识点小结
- 数组的排序处理；
- 分治思想的应用；
- 递归结果的返回处理；