【组合回溯递归】【树层去重used标记】Leetcode 40. 组合总和 II

---------------🎈🎈40. 组合总和 II 题目链接🎈🎈-------------------

解法 组合问题常用解法 + 树层去重

问题描述：（数组candidates）有重复元素，但还不能有重复的组合
操作：去重的是“同一树层上的使用过的元素”
核心：加入一个used数组，去重时结合：前后数字相同的判断 + used[i-1]未被使用的判断，若成立则continue当前for遍历

如果candidates[i] == candidates[i - 1]
并且 used[i - 1] == false（即前一个元素没有被使用时）
此时for循环里就应该做continue的操作。

说明：

used[i - 1] == true，说明同一树枝candidates[i - 1]使用过.
used[i - 1] == false，说明同一树层candidates[i - 1]使用过.

为什么 used[i - 1] == false 就是同一树层呢？？
因为同一树层，used[i - 1] == false 才能表示：当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。
而 used[i - 1] == true，说明是进入下一层递归，取下一个数，所以是树枝上

时间复杂度O(N)
空间复杂度O(N)

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        int[] used = new int[candidates.length]; // 初始化一个used数组 均为0， 表示都没有使用
        helper(candidates,target,0,0,used);
        return result;

    }
    public void helper(int[] candidates, int target, int startnum, int sum, int[] used){
        // 终止条件
        if(sum==target){ 
            result.add(new ArrayList<>(temp));
        }
        if(sum>target){
            return;
        }

        // 树层去重
        
        for(int i = startnum; i<candidates.length; i++){
            // 当前面的一个元素和现在的元素相同，且前面一个元素并未被使用的时候，跳过（因为所有可能都已经被前面的元素查找过了）
            if(i>0 && used[i-1]!=1 && candidates[i] == candidates[i-1]){  
                continue;
            }
            used[i] = 1; // 置为一：标志着第i个元素被使用
            sum+=candidates[i];
            temp.add(candidates[i]);
            helper(candidates,target,i+1,sum,used); // 递归
            temp.removeLast();
            sum-=candidates[i];
            used[i] = 0; // 回溯恢复

        }
    }
}      
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38