题目链接：https://leetcode.com/problems/combination-sum/

 

解题思路：

这是非常典型的DFS并且返回路径的题目，我们采用DFS的方法，在搜索之前我们首先进行排序，因为数组有可能是乱序的。

同时，这道题还要判断重复解。用我之前介绍的方法：

 if(!res.contains(item)) 
                res.add(new ArrayList<Integer>(item)); 

 

还是老问题，用DFS找解决方案，不同点是，这道题： The same repeated number may be chosen from C unlimited number of times.

所以，每次跳进递归不用都往后挪一个，还可以利用当前的元素尝试。

 

 1 import java.util.ArrayList;
 2 class Solution {
 3     public List<List<Integer>> combinationSum(int[] candidates, int target) {
 4         
 5         List<List<Integer>> res= new ArrayList<>();
 6         List<Integer> item = new ArrayList<>();
 7         
 8         if(candidates==null||candidates.length==0)
 9             return res;
10         Arrays.sort(candidates);
11         
12         helper(res,item,0,target,candidates);
13         
14         return res;
15     }
16     public void helper( List<List<Integer>> res,List<Integer> item,int start,int target,int []candidates)
17     {
18         if(target<0)
19             return ;
20         if(target==0)
21         {
22             if(!res.contains(item))
23             {
24                 res.add(new ArrayList<Integer>(item));
25             }
26         }
27         
28         for(int i=start;i<candidates.length;i++)
29         {
30             item.add(candidates[i]);
31             int newtarget = target - candidates[i];
32             
33             helper(res,item,i,newtarget,candidates);
34             ////先加入元素，然后进行搜索，这里进行DFS搜索，如果不满足，就把temp列表里的元素去除掉
35             item.remove(item.size()-1); 
36             ////目标和不符合，所以将临时列表的最新值去除，然后尝试下一个元素
37         }
38     }
39 }