回溯搞定组合总和

看到这道题，第一下想到用回溯模板。
直接上代码：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ArrayList<Integer> temp = new ArrayList<>();
        dfs(temp, target, candidates, 0);
        return res;
    }

    public void dfs(ArrayList<Integer> temp, int target, int[] candidates, int start){
        if(target == 0){
            res.add(new ArrayList(temp));
            return;
        }
        for(int i = start; i < candidates.length; i++){
            if(i > start && candidates[i] == candidates[i-1]) continue; //去重
            if(candidates[i] <= target){ //剪枝
                temp.add(candidates[i]);
                dfs(temp, target - candidates[i], candidates, i);    //这里注意 如果每个数字在组合中只能有一个 最后参数应为i+1
                temp.remove(temp.size() - 1);
            }
        }
        return;
    }
}