給定一個(gè)數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。
candidates 中的每個(gè)數(shù)字在每個(gè)組合中只能使用一次。

示例 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]
]

class Solution {
    private List<List<Integer>> list = new ArrayList<>();

    private List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates.length == 0 || (candidates.length == 1 && candidates[0] != target)) {
            return list;
        }
        Set<Integer> set = new HashSet<>();
        for (int candidate : candidates) {
            set.add(candidate);
        }
        Integer[] candidate = set.toArray(new Integer[0]);
        List<Integer> myList = new ArrayList<>();
        test(candidate, target, 0, myList);
        return list;
    }
    private void test(Integer[] candidate, int target, int start, List<Integer> myList) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            list.add(new ArrayList<>(myList));
        }
        for (int i = start; i < candidate.length; i++) {
            myList.add(candidate[i]);
            test(candidate, target - candidate[i], i + 1, myList);
            myList.remove(myList.size() - 1);
        }
    }
}

• list.toArray(new Integer[0])可以得到一個(gè)指定泛型的數(shù)組
  思路是先用set去重再進(jìn)行回溯求和
  測試數(shù)據(jù) combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8)
  結(jié)果少了個(gè)結(jié)果[1,1,6] 自己理解錯(cuò)了
  是只允許出現(xiàn)一次不是不允許重復(fù)

力扣上的做法

   private void process(int start, int[] candidates, int target, List<Integer> list) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            lists.add(new ArrayList<>(list));
        } else {
            for (int i = start; i < candidates.length; i++) {
                //因?yàn)檫@個(gè)數(shù)和上個(gè)數(shù)相同，所以從這個(gè)數(shù)開始的所以情況，在上個(gè)數(shù)里面都考慮過了，需要跳過
                if (i > start && candidates[i] == candidates[i - 1]) {
                    continue;
                }
                list.add(candidates[i]);
                process(i + 1, candidates, target - candidates[i], list);
                list.remove(list.size() - 1);
            }
        }
作者：reedfan
鏈接：https://leetcode-cn.com/problems/combination-sum-ii/solution/di-gui-hui-su-jiang-jie-chao-xiang-xi-by-reedfan/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

如果有重復(fù)就是在子樹里循環(huán)重復(fù),這里作者在遞歸之前先進(jìn)行了排序Arrays.sort(candidates) 所以只要和之前的的循環(huán)進(jìn)行比對,就把去重做好了

總結(jié)

回溯法 也是遞歸的一種應(yīng)用,也走不出自己調(diào)用自己的框架
回溯的精華在于:

1. 不管成功失敗
   (即遞歸結(jié)束)
2. 都進(jìn)行回溯
   (即把集合的最后一位消除)
3. 嘗試新的可能,
   (開始新的一輪循環(huán))
4. 如果符合條件 加到總集合中,
   (lists.add(new ArrayList<>(list));)
5. 如果不符合條件,結(jié)束遞歸
   (return)