40. 组合总和 II

给定一个数组 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] ]

思路

这道题目和39.组合总和 (opens new window)如下区别:

  1. 本题candidates 中的每个数字在每个组合中只能使用一次。
  2. 本题数组candidates的元素是有重复的,而39.组合总和 (opens new window)是无重复元素的数组candidates

最后本题和39.组合总和 (opens new window)要求一样,解集不能包含重复的组合。

本题的难点在:集合(数组candidates)有重复元素,但还不能有重复的组合。

用set或者map去重,这么做很容易超时!

所谓去重,其实就是使用过的元素不能重复选取。 这么一说好像很简单!

都知道组合问题可以抽象为树形结构,那么“使用过”在这个树形结构上是有两个维度的,一个维度是同一树枝上使用过,一个维度是同一树层上使用过。

那么问题来了,我们是要同一树层上使用过,还是同一树枝上使用过呢?

回看一下题目,元素在同一个组合内是可以重复的,怎么重复都没事,但两个组合不能相同。

所以我们要去重的是同一树层上的“使用过”,同一树枝上的都是一个组合里的元素,不用去重。

举一个例子,candidates = [1, 1, 2], target = 3,(方便起见candidates已经排序了)

强调一下,树层去重的话,需要对数组排序!

选择过程树形结构如图所示:

 

40. 组合总和 II

 

可以看到图中,每个节点相对于 39.组合总和 (opens new window)我多加了used数组

回溯三部曲

  • 递归函数参数

39.组合总和 (opens new window)套路相同,此题还需要加一个bool型数组used,用来记录同一树枝上的元素是否使用过。

这个集合去重的重任就是used来完成的。

  • 递归终止条件

39.组合总和 (opens new window)相同,终止条件为 sum > target 和 sum == target

sum > target 这个条件其实可以省略,因为和在递归单层遍历的时候,会有剪枝的操作

  • 单层搜索的逻辑

这里与39.组合总和 (opens new window)最大的不同就是要去重了。

前面我们提到:要去重的是“同一树层上的使用过”,如何判断同一树层上元素(相同的元素)是否使用过了呢。 

如果candidates[i] == candidates[i - 1] 

并且 used[i - 1] == false

就说明:前一个树枝,使用了candidates[i - 1],也就是说同一树层使用过candidates[i - 1]。

此时for循环里就应该做continue的操作。

这块比较抽象,如图:

 

40. 组合总和 II

 

我在图中将used的变化用橘黄色标注上,可以看出在candidates[i] == candidates[i - 1]相同的情况下:

  • used[i - 1] == true,说明同一树支candidates[i - 1]使用过
  • used[i - 1] == false,说明同一树层candidates[i - 1]使用过
class Solution {
    List<List<Integer>> lists = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    int sum = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //为了将重复的数字都放到一起,所以先进行排序
        Arrays.sort(candidates);
        //加标志数组,用来辅助判断同层节点是否已经遍历
        boolean[] flag = new boolean[candidates.length];
        backTracking(candidates, target, 0, flag);
        return lists;
    }

    public void backTracking(int[] arr, int target, int index, boolean[] flag) {
        if (sum == target) {
            lists.add(new ArrayList(path));
            return;
        }
        for (int i = index; i < arr.length && arr[i] + sum <= target; i++) {
            //出现重复节点,同层的第一个节点已经被访问过,所以直接跳过
            if (i > 0 && arr[i] == arr[i - 1] && !flag[i - 1]) {
                continue;
            }
            flag[i] = true;
            sum += arr[i];
            path.push(arr[i]);
            //每个节点仅能选择一次,所以从下一位开始
            backTracking(arr, target, i + 1, flag);
            int temp = path.pop();
            flag[i] = false;
            sum -= temp;
        }
    }
}

  

上一篇:深度优先搜索实现回溯算法


下一篇:LeetCode-100题(Hot) 40. 组合总和 II [Java实现] [极速]