https://leetcode.com/problems/combination-sum/

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

 

For example, given candidate set 2,3,6,7 and target 7, 

A solution set is: 

[7] 

[2, 2, 3] 

解题思路：

这仍然是一道permutation的题目，考虑用DFS。

掌握了前面N道DFS的题目，这里的思路应该非常清晰了。遇到的问题有两个，第一，结果的数字要升序。第二，结果不能有重复的组合。

第一个问题比较好解决，处理开始就将数组排序即可。

第二个问题要考虑下，方法一：将结果算出来，塞进List<List<Integer>>的时候看是不是已经存在。方法二：避免算出重复的结果。我这里用了第二种方法，其实和前面visited数组的标记很像。

跑一下未处理重复的程序可以发现，重复的答案都是，[2, 2, 3]和[3, 2, 2]这种。所以递归的时候，只选取当前元素往后的元素就可以了。往前的因为已经选过，可以不选。这样就避免了重复的答案。

public class Solution {    public List
     
      
       > combinationSum(int[] candidates, int target) {        List
       
        
         > resultList = new LinkedList
         
          
           >(); List
           
             currentList = new LinkedList
            
             (); //原题没说数组已经排序了，必须先排序 Arrays.sort(candidates); dfs(resultList, currentList, 0, 0, candidates, target); return resultList; } public void dfs(List
             
              
               > resultList, List
               
                 currentList, int currentSum, int step, int[] candidates, int target){ if(currentSum == target){ resultList.add(new LinkedList(currentList)); return; } if(currentSum > target){ return; } //避免结果重复的方法：i从当前元素开始往后开始，所以要把当前元素作为参数传进方法 for(int i = step; i < candidates.length; i++){ currentList.add(candidates[i]); currentSum += candidates[i]; dfs(resultList, currentList, currentSum, i, candidates, target); currentList.remove(currentList.size() - 1); currentSum -= candidates[i]; } }}
               
              
             
            
           
          
         
        
       
      
     

仍然要注意的是，必须是resultList.add(new LinkedList(currentList))，而不能直接resultList.add(currentList)。

最后要注意特别重要的一点，题目给出的是，Given a set of candidate numbers (C) and a target number (T)，也就是数组中是没有重复元素的，否则例如[1,1,1,1,1]，1。即便从当前元素往后搜索，仍然会有重复答案。