leetcode 39. 组合总和

这道题目看上去的第一眼我就想用dfs做，毕竟暴力一点的方法比较好想。

在第一次实现后，我发现最后的结果会有一部分重复项，比如：

题目：
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]
我的结果：

所求解集为:
[
  [7],
  [2,2,3]，

  [2,3,2]

  [3,2,2]

]
可以发现我的结果会有一部分重复项，后来我对dfs方法中的循环做了一些简单的处理。
也就是，当开始加入下一个位置的数字后，以后的每一次调用，都不会加入这个位置之前的数字。
上代码

 1 class Solution {
 2     public List<List<Integer>> list=new ArrayList();
 3     public List<List<Integer>> combinationSum(int[] candidates, int target) {
 4         List li=new ArrayList();
 5         dfs(candidates,target,0,li,0);
 6         return list;
 7     }
 8     public void dfs(int[] candidates, int target,int total,List li,int step){
 9         if(total==target) {
10             List ll=new ArrayList(li);
11             list.add(ll);
12             return;
13         }
14         else
15             for(int n=step;n<candidates.length;++n)
16                 if(total+candidates[n]<=target) {
17                     li.add(candidates[n]);
18                     System.out.println(li);
19                     dfs(candidates,target,total+candidates[n],li,n);
20                     li.remove(li.size()-1);
21                 }
22     }
23 }

这样就可以完美解决了