40.组合总和II

树图

去重

• 同一层出现相同的数要去重
• 一条路径中允许出现重复数字
• 使用一个数组used来记录当前数字是否被使用，每次递归都传入这个数组，可以做区分统一层中遇到的重复和在一条路径中遇到重复这两种情况。如果candidates[i] == candidates[i-1] && !used[i-1] 则在同一层中遇到重复，剪枝。

import java.util.Arrays;
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList();
    boolean[] used;
    int sum = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        Arrays.fill(used, false);
        Arrays.sort(candidates);
        backTracking(candidates, target, 0);
        return result;
    }
    public void backTracking(int[] candidates, int target, int index){
        // if(sum > target){
        //     return ;
        // }
        if(sum == target){
            result.add(new ArrayList(path));
            // return ;
        }
        for(int i = index ; i < candidates.length ; i++){
            if (sum + candidates[i] > target) {
                break;
            }
            if(i>0 && candidates[i] == candidates[i-1] && !used[i-1]){
                continue ;
            }
            used[i] = true;
            sum += candidates[i];
            path.add(candidates[i]);
            backTracking(candidates, target, i+1);
            used[i] = false;
            sum -= candidates[i];
            path.removeLast();
        }
    }
}