LeetCode#40数组加起来Ⅱ

给定一个数组 candidates 还有一个目标号码 target ，找出 candidates 所有人都能把数字相加。 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

包括目标数在内的所有数都是正整数。
解决方案集不能包含重复的组合。
示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
求解集为:
[
[1,2,2],
[5]
]

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

class Solution_40 {
    public List> combinationSum2(int[] candidates, int target) {
        List> res = new ArrayList<>();
        Deque path = new ArrayDeque<>();
        if (candidates.length == 0) {
            return res;
        }
        // 数组正序排序, 如果你想知道更多，你可以去百度。。 Arrays.sort用法
        Arrays.sort(candidates);
        dfs(candidates, 0, candidates.length, target, path, res);
        System.out.println(res);
        return res;
    }

    public void dfs(int[] candidates, int begin, int len, int target, Deque path, List> res) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = begin; i < len; i++) {
              // 大剪枝
              if (target - candidates[i] < 0) {
                break;
            }

            // 小剪枝  这里的重点是, 如果希望结果集中没有重复的元素，可以 i>0
            if ( i > begin && candidates[i] == candidates[i - 1]) {
                continue;
            }

            path.add(candidates[i]);
            dfs(candidates, i+1, len, target - candidates[i], path, res);
            path.removeLast();
        }
    }
    public static void main(String[] args) {
        int[] a = { 2, 5, 2, 1,2 };
        Solution_40 s = new Solution_40();
        s.combinationSum2(a, 5);
    }
}

在思考时避免重复是非常重要的。 该方法最重要的功能是同一级别不具有相同的元素。我。

              1
             / 
            2   2  这不会发生 但它允许不同级别之间的重复，即：
           /     
         5       5
            例2
              1
             /
            2      这种情况确实是允许的。
           /
          2  
             为什么会有这么神奇的效果？ 
       首先 cur-1 == cur 用于确定当前元素是否与前一元素相同的语句。这句话可以省略这个例子1。

然而，问题出现了。如果所有当前和先前的元件都被切断，则示例2的情况也将消失。 因为当第二次2当他出现时，他和前一个在一起。2相同了。
那么，如何保留示例2呢？ 那么就用cur > begin 为了避免这种情况，您可以找到一个例子。1中的两个2处于同一水平， 例2的两个2处于不同的级别。
在一个for在循环中，遍历的所有数字都属于一个级别。我们将建立一个层次结构，
必须出现且只有一个2，然后放开第一个副本2，但不要放过后者2。 第一个出现2特性 cur == begin.
第二次亮相2 特点是cur > begin.

主要参考上述代码思想。 liweiwei1419
报价解释来自 Allen
本文仅供记录LeetCode所见， 分享你所看到的，
如果侵权，请迅速删除。

主题来源：力扣(LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii
版权归网络所有。商业转载请联系官方授权，并注明非商业转载的来源。