题目

image.png

思路

  • 与组合总和差不多，关键在于如何去重。

    ```basic 解释语句: if cur > begin and candidates[cur-1] == candidates[cur] 是如何避免重复的。 这个避免重复当思想是在是太重要了。 这个方法最重要的作用是，可以让同一层级，不出现相同的元素。即

    1.             1
    2.            / \
    3.           2   2  这种情况不会发生 但是却允许了不同层级之间的重复即：
    4.          /     \
    5.         5       5
    6.           例2
    7.             1
    8.            /
    9.           2      这种情况确是允许的
    10.          /
    11.         2

为何会有这种神奇的效果呢？ 首先 cur-1 == cur 是用于判定当前元素是否和之前元素相同的语句。这个语句就能砍掉例1。 可是问题来了，如果把所有当前与之前一个元素相同的都砍掉，那么例二的情况也会消失。 因为当第二个2出现的时候，他就和前一个2相同了。

那么如何保留例2呢？ 那么就用cur > begin 来避免这种情况，你发现例1中的两个2是处在同一个层级上的， 例2的两个2是处在不同层级上的。 在一个for循环中，所有被遍历到的数都是属于一个层级的。我们要让一个层级中， 必须出现且只出现一个2，那么就放过第一个出现重复的2，但不放过后面出现的2。 第一个出现的2的特点就是 cur == begin. 第二个出现的2 特点是cur > begin.


<a name="M26Ak"></a>
### 代码
```java
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates, target, 0, res, new ArrayList<>());
        return res;
    }

    public void dfs(int[] candidates, int target, int index, List<List<Integer>> res, List<Integer> tmp) {
        if (0 == target) res.add(new ArrayList<>(tmp));
        if (target <= 0) return;
        for (int i = index; i < candidates.length; i++) {
            //剪枝处理
            if (target < candidates[i]) return;
            //去重处理
            if(i > index && candidates[i] == candidates[i-1]) continue;
            tmp.add(candidates[i]);
            dfs(candidates, target - candidates[i], i + 1, res, tmp);
            tmp.remove(tmp.size() - 1);
        }
    }

组合总和 II