题目

题解

代码

import java.util.*;

public class code40 {

    public static int sum = 0;

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(res, list, candidates, target, 0);
        return res;
    }

    public static void backtrack(List<List<Integer>> res, List<Integer> list, int candidates[], int target, int start) {
        if (sum == target) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            // 剪枝的前提是数组升序排序
            if (sum + candidates[i] <= target) {
                // [1, 1, 2, 5, 6, 7, 10]
                // 0 号索引的 1 ，从后面 6 个元素中搜索
                // 1 号索引也是 1 ，从后面 5 个元素（是上面 6 个元素的真子集）中搜索，这种情况显然上面已经包含。

                if ((i > start) && (candidates[i] == candidates[i - 1])) { // 在递归调用的统一深度（层）中，一个元素只使用一次。
                    continue;
                }
                // 【我添加的代码在这里】：
                // 1、i > start 表明剪枝的分支一定不是当前层的第 1 个分支
                // 2、candidates[i - 1] == candidates[i] 表明当前选出来的数等于当前层前一个分支选出来的数
                // 因为前一个分支的候选集合一定大于后一个分支的候选集合
                // 故后面出现的分支中一定包含了前面分支出现的结果，因此剪枝
                // “剪枝”的前提是排序，升序或者降序均可

                list.add(candidates[i]);
                sum += candidates[i];
                backtrack(res, list, candidates, target, i + 1); // 【关键】因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
                sum -= candidates[i];
                list.remove(list.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        int[] candidates1 = { 10, 1, 2, 7, 6, 1, 5 };
        int target1 = 8;
        List<List<Integer>> combinationSum1 = combinationSum2(candidates1, target1);
        System.out.println(combinationSum1);

        int[] candidates2 = { 2, 5, 2, 1, 2 };
        int target2 = 5;
        List<List<Integer>> combinationSum2 = combinationSum2(candidates2, target2);
        System.out.println(combinationSum2);

    }
}
40. 组合总和 II

题目

题解

代码

参考
