Leetcode组合总和+剪枝

Leetcode39.组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

如图，首先有四种选择方法，可以在2,3,6.7中任选一个，然后将它加到临时列表中去，之后每层都有四种选择方法（因为可重复选择)，每次选择后我们用sum+=选择的值，当我们一直选择到sum等于target的时候，说明我们找到了一种情况满足条件，那我们就将这一临时列表加到结果列表里去，如果sum>target,则说明当前的值不应该选择，直接return即可。只有当sumtarget时，才可以进行下去，遍历整数数组，然后加入当前数值，回溯，撤销。

public static void main(String[] args) {
    
        int[] candidates={
    2,3,6,7};
        int target=7;
        List<List<Integer>> list = combinationSum(candidates, target);
        System.out.println(list);
    }
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
    
        List<List<Integer>> list=new ArrayList<>();
        List<Integer> path=new ArrayList<>();
        Arrays.sort(candidates);//必须先排序，防止重复
        dfs(list,candidates,0,0,target,path);

        return list;
    }
    private static void dfs(List<List<Integer>> list, int[] nums, int start, int sum, int target, List<Integer> path) {
    
        if(sum==target){
    
            list.add(new ArrayList<>(path));
            return;
        }
        if (sum>target)//可有可无
            return;
        for (int i = start; (i < nums.length&&sum+nums[i]<=target); i++) {
    //如果sum大于target就没有必要循环了
            path.add(nums[i]);
            dfs(list,nums,i,sum+nums[i],target,path);
            path.remove(path.size()-1);
        }
    }