40. 组合总和 II-LeetCode

40. 组合总和 II-LeetCode

心得:主要用到回溯和剪枝,一定要把剪枝的条件想全了,要不然时间会多很多

这里去重的地方要好好注意一下,如何去重的,能不用set尽量不用,比较优雅。

尽量把条件写的紧凑一点,能在一个递归里处理的在一个递归里处理,把条件改变

写在递归方法里,然后再去处理,这样代码量小,而且优雅。

 1 class Solution {
 2       public List<List<Integer>> combinationSum2(int[] candidates, int target){
 3            LinkedList<List<Integer>> list=new LinkedList<>();
 4             if(candidates==null||candidates.length==0)
 5                 return list;
 6             Arrays.sort(candidates);
 7             rec(0,list,new LinkedList<Integer>(),candidates,target);
 8             return list;
 9         }
10     public void rec(int index,LinkedList<List<Integer>> list,LinkedList<Integer> tmp,int[] candidates,int target)
11        {
12          if(target<0)
13              return;
14          else if(target==0)
15          {        
16              list.add(new LinkedList(tmp));
17              return;
18          }
19          else
20          {
21              for(int i=index;i< candidates.length&&candidates[i]<=target;i++)//这个剪枝条件就可以提高
//速度 22 { 23 if(i!=index&&candidates[i]==candidates[i-1]) 24 continue; 25 tmp.add(candidates[i]); 26 rec(i+1,list,tmp,candidates,target-candidates[i]); 27 tmp.removeLast(); 28 } 29 } 30 } 31 }

 

上一篇:39. Combination Sum


下一篇:39. 组合总和 -LeetCode