leetcode题目40. 组合总和 II（java）

题目描述

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的 每个数字在每个组合中只能使用一次。所有数字（包括目标数）都是正整数。解集不能包含重复的组合。

示例

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

代码

public List<List<Integer>> combinationSum_II(int[] candidates, int target) {

    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    Arrays.sort(candidates); // 排序
    dfs_II(candidates, target, result, path, 0);
    return result;
}

public void dfs_II(int[] candidates, int target, List<List<Integer>> result, LinkedList<Integer> path, int begin) {
    if (target == 0) {
        // 找到了一条路径，将路径拷贝一份儿放到结果数组里
        result.add(new ArrayList<Integer>(path));
        return;
    }
    for (int i = begin; i < candidates.length; i ++) {
        if (candidates[i] > target) {
            // 剪枝，去除没必要的搜索
            return;
        }

        if (i > begin && candidates[i] == candidates[i - 1]) {
            // 剪枝，因为不允许重复，所以如果当前的值已经计算过了，就不再处理了
            continue;
        }

        path.add(candidates[i]);
        dfs_II(candidates, target - candidates[i], result, path, i + 1); // 递归
        path.removeLast(); // 每次回溯将最后一次加入的元素删除
    }
}