Combination Sum -- LeetCode

这个题是一个NP问题，方法仍然是N-Queens中介绍的套路。基本思路是先排好序，然后每次递归中把剩下的元素一一加到结果集合中，并且把目标减去加入的元素，然后把剩下元素（包括当前加入的元素）放到下一层递归中解决子问题。算法复杂度因为是NP问题，所以自然是指数量级的。代码如下：

public ArrayList
  
   > combinationSum(int[] candidates, int target) {
    ArrayList
   
    > res = new ArrayList
    
     >(); if(candidates == null || candidates.length==0) return res; Arrays.sort(candidates); helper(candidates,0,target,new ArrayList
     
      (),res); return res; } private void helper(int[] candidates, int start, int target, ArrayList
      
        item, ArrayList
       
        > res) { if(target<0) return; if(target==0) { res.add(new ArrayList
        
         (item)); return; } for(int i=start;i
         
          0 && candidates[i]==candidates[i-1]) continue; item.add(candidates[i]); helper(candidates,i,target-candidates[i],item,res); item.remove(item.size()-1); } }