LC40. 组合总和 II

?代码随想录

class Solution {

    List<Integer> path = new ArrayList<>();

    List<List<Integer>> res = new ArrayList<>();

    int sum = 0 ;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtracking(candidates,target,0);
        return res;
    }

    public void backtracking(int [] candidates, int target, 
                        int startIndex){
        if(sum == target){
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = startIndex ; i < candidates.length; i ++){
            
            if(i > startIndex && candidates[i] == candidates[i-1]){
                continue;
            }

            if(sum + candidates[i] > target){
                break;
            }

            path.add(candidates[i]);
            
            sum += candidates[i];
            backtracking(candidates,target,i + 1);

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


    }

}