4. ＜ tag backtracking, combination and pruning ＞ lt.39 Combined sum + lt.40 Combined sum II DBC

lt.39. Combinatorial summation

[ Case needs ]

[ Thought analysis ]

[ Code implementation one , Non pruning optimization method ]

class Solution {
    
    List<List<Integer>> lists = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    
        if(candidates.length == 0  || candidates == null){
    
            return lists;
        }

        backTracking(candidates, target, 0, 0);

        return lists;
    }

    public void backTracking(int[] candidates, int target, int sum, int startIndex){
    
        // Recursion end condition 
        if(sum > target)return;
        if(sum == target){
    
            lists.add(new ArrayList<>(path));
            return;
        }

        // Single layer recursive logic 
        for(int i = startIndex; i < candidates.length; i++){
    
            sum += candidates[i];
            path.add(candidates[i]);

            backTracking(candidates, target, sum, i);

            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

[ Code implementation one , Pruning optimization solution ]

lt.40. Combinatorial summation II

[ Case needs ]

[ Thought analysis ]

[ Code implementation one , Non pruning optimization method ]

class Solution {
    
    List<List<Integer>> lists = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    
        boolean[] used = new boolean[candidates.length];
        Arrays.sort(candidates);    
        backTracking(candidates, target, 0, 0, used);
        return lists;
    }

    public void backTracking(int[] candidates, int target, int sum, int startIndex, boolean[] used){
    
        if(sum > target)return;
        if(sum == target){
    
            lists.add(new ArrayList<>(path));
            return;
        }
        
        // Single layer recursive logic 
        for(int i = startIndex; i < candidates.length; i++){
    
            // duplicate removal 
            if(i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false)continue;
            sum += candidates[i];
            used[i] = true;
            path.add(candidates[i]);

            backTracking(candidates, target, sum, i + 1, used);

            sum -= candidates[i];
            used[i] = false;
            path.remove(path.size() - 1);    
        }
    }
}

[ Code implementation 2 , Pruning optimization solution ]