[数据结构与算法]组合总和

深度递归 剪枝

深度递归 剪枝 50% 72.27%
深度递归，不断减去数组序列中的值，直到减到 target < 0，
剪枝的过程：idx 为简直过程；
如：深度为 1 时，递归 for 循环第一层，会将所有减1的情况包含，
所以 for 循环第二次时候，从 index=2 开始（即candidates[2]），不用再减去 candidates[1] 的数。
for 循环第三次时候，index=3， 不用减 candidates[1]、candidates[2] 的元素
……

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> rs = new ArrayList<>();
        List<Integer> calList = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates, 0, target, calList, rs);
        return rs;
    }

    public void dfs(int[] candidates, int idx, int target, List<Integer> list, List<List<Integer>> rs){
        for(int i = idx; i < candidates.length; i++){
            if(target - candidates[i] < 0){
                break;
            }else if(target - candidates[i] == 0){
                list.add(candidates[i]);
                rs.add(new ArrayList<>(list));
                list.remove(list.size()-1);
                break;
            }else {
                list.add(candidates[i]);
                dfs(candidates, i,target-candidates[i], list, rs);
                list.remove(list.size()-1);
            }
        }
    }
}