题目

image.pngimage.png

注意事项

剪枝 需保证数组有序（结合题意：要保证后面的加和大于前面的加和）

剪枝提速

  • 根据上面画树形图的经验，如果 target 减去一个数得到负数，那么减去一个更大的树依然是负数，同样搜索不到结果。基于这个想法，我们可以对输入数组进行排序，添加相关逻辑达到进一步剪枝的目的；
  • 排序是为了提高搜索速度，对于解决这个问题来说非必要。但是搜索问题一般复杂度较高，能剪枝就尽量剪枝。实际工作中如果遇到两种方案拿捏不准的情况，都试一下。

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解题代码

  1. class Solution {
  2.     //存放结果集
  3.     List< List<Integer> > result = new ArrayList<>();
  4.     //收集路径
  5.     LinkedList<Integer> path = new LinkedList<>();
  7.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  9.         Arrays.sort(candidates);
  10.         backtracking(candidates,target,0,0);
  11.         return result;
  12.     }
  14.     public void backtracking(int[] candidates, int target, int sum, int startIndex ) {
  15.         if(sum > target ) {
  16.             return ;
  17.         }
  19.         if(sum == target ) {
  20.             result.add(new ArrayList<>(path));
  21.             return ;
  22.         }
  24.         for(int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++ ) {
  25.             sum += candidates[i];
  26.             path.add(candidates[i]);
  27.             //注意此时是i(可重复使用)
  28.             backtracking(candidates,target,sum, i );
  29.             path.removeLast(); // 与上面操作对应
  30.             sum -= candidates[i]; // 与上面操作对应
  31.         }
  32.     }
  33. }