LeetCode40- Total number of combinations II

One 、 Title Description

Two 、 Backtracking tree

Combination is a typical problem of finding a subset of a sequence , The limitation in the title is that the sequence found cannot be repeated , So this is also very simple , Just sort the original sequence in ascending order , When the backtracking tree expands horizontally （for loop ）, Skip the repeated elements directly （ No recursion , See code for details ）

3、 ... and 、 Total number of combinations II Code implementation

class Solution {
    
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    
        List<List<Integer>> res = new ArrayList<>();
        //  You have to sort here first , Because it's going to be heavy 
        Arrays.sort(candidates);
        solve(candidates, target, res, new ArrayList<>(), 0, 0);
        return res;
    }

    public void solve(int[] candidates, int target, List<List<Integer>> res, List<Integer> curRes, int startIndex, int curSum) {
    
        if (curSum == target) {
    
            //  It needs to be recorded 
            res.add(new ArrayList<>(curRes));
            return;
        } 

        if (curSum > target) {
    
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
    
            if (curSum + candidates[i] > target) {
    
                break;
            }
            //  After the first , It is necessary to judge whether weight removal is necessary 
            if (i > startIndex) {
    
                //  Lateral weight removal 
                if (candidates[i] == candidates[i - 1]) {
    
                    continue;
                }
            }
            curSum += candidates[i];
            curRes.add(candidates[i]);
            solve(candidates, target, res, curRes, i + 1, curSum);
            curSum -= candidates[i];
            curRes.remove(curRes.size() - 1);
        }
    }
}