组合总数II

一、题目

 

二、代码 

此题与上题的不同在于候选数组存在相同的数字，而且最终的组合中，候选数组中每个数字只能出现一次 ，如何去重是本题的难点，可以[2,5,2,1,2]为例。

class Solution {
    List<List<Integer>> result = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target){
        //visited 路径
        List<Integer> visited = new LinkedList<>();
        Arrays.sort(candidates);
        //选择列表 candidates
        backtrack(visited, candidates,target, 0);
        return result;

    }
 // public void backtrack(路径，选择列表){
//     if(满足结束条件){
//         result.add(结果);
//     }
//     for(选择：选择列表){
//         做出选择;
//         backtrack(路径，选择列表);
//         撤销选择;
//     }

//引入start的目的是为了去重，重复的原因是在较深层的结点值考虑了之前考虑过的元素，所以需要设置下一轮搜索的起点
    public void backtrack(List<Integer> visited, int[] candidates, int target, int start){
        if(target < 0){
            return;
        }
        if(target == 0){
            result.add(new LinkedList(visited));
            return;
        }
        for(int i = start; i < candidates.length; i++){
//去重。对于[1,2,2,2,5]中，start = 0,i = 2时，跳过循环，如果不跳过，会出现重复的组合
            if(i > start && candidates[i] == candidates[i - 1]){
                continue;
            }
            visited.add(candidates[i]);
            backtrack(visited, candidates, target - candidates[i], i + 1);
            visited.remove(visited.size() - 1);

        }
    }


}