Leetcode combination sum + pruning

Leetcode39. Combinatorial summation

To give you one No repeating elements Array of integers for candidates And a target integer target , find candidates You can make the sum of numbers as the target number target Of all Different combinations , And return... As a list . You can press In any order Return these combinations .

 Input ：candidates = [2,3,6,7], target = 7
 Output ：[[2,2,3],[7]]
 explain ：
2  and  3  Can form a set of candidates ,2 + 2 + 3 = 7 . Be careful  2  You can use it multiple times .
7  Is also a candidate , 7 = 7 .
 Only these two combinations .

Pictured , First, there are four options , Can be in 2,3,6.7 Choose one of them , Then add it to the temporary list , After that, there are four selection methods for each layer （ Because it can be selected repeatedly ), After each selection, we use sum+= Selected value , When we choose until sum be equal to target When , It shows that we have found a situation that meets the condition , Then we will add this temporary list to the result list , If sum>target, It means that the current value should not be selected , direct return that will do . Only when sumtarget when , Can proceed , Traversing an array of integers , Then add the current value , to flash back , revoke .

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);// You have to sort , Prevent duplication 
        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)// not essential 
            return;
        for (int i = start; (i < nums.length&&sum+nums[i]<=target); i++) {
    // If sum Greater than target There is no need to cycle 
            path.add(nums[i]);
            dfs(list,nums,i,sum+nums[i],target,path);
            path.remove(path.size()-1);
        }
    }