[leetcode]Combination sum

典型的DFS吧 这一类还有permutation啊，求组合啊，之类的~~~

代码：

public class Solution {
    private ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(candidates == null||candidates.length == 0) return null;
        int len = candidates.length;
        Arrays.sort(candidates);
        result.clear();
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        dfs(candidates,target,list,0);
        return result;
        
    }
    
    public void dfs(int[]a,int key, ArrayList<Integer> list,int i){
        if(key == 0){//找到解
            ArrayList<Integer> temp = new ArrayList<Integer>();
            temp.addAll(list);
            result.add(temp);
            return;
        }
        if(i == a.length) return;
        dfs(a,key,list,i+1);//不选择a[i];
        int count = 1;
        while(a[i]*count <= key){//重复选择a[i]
            for(int j = 1;j<=count;j++)
               list.add(a[i]);
            dfs(a,key-a[i]*count,list,i+1);
            for(int j = 1;j<=count;j++)
                list.remove(list.size()-1);
            count++;
        }
    }
}

 Combination Sum II

//待补充~