LeetCode刷题复盘笔记——40. 组合总和 II（一文搞懂回溯解决有重集合中结果去重的组合问题）

今日主要总结一下，40. 组合总和 II

题目：40. 组合总和 II

Leetcode题目地址

题目描述：
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

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

注意：解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

本题重难点

大家在做这道题之前最好做一下77. 组合
和216. 组合总和 III这两道题，或者看一下一文搞懂回溯解决组合问题我对这两道题有详细的讲解

这道题目和题目39.组合总和如下区别：

本题candidates 中的每个数字在每个组合中只能使用一次。
本题数组candidates的元素是有重复的，而39.组合总和是无重复元素的数组candidates
最后本题和题目39.组合总和要求一样，解集不能包含重复的组合。

本题的难点在于：输入数组candidates有重复元素，输出但还不能有重复的组合。

一些同学可能想了：我把所有组合求出来，再用set或者map去重，这么做很容易超时！

所以要在搜索的过程中就去掉重复组合。

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

都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过”
是造成大家没有彻底理解去重的根本原因。

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

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

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

为了理解去重我们来举一个例子，candidates = [1, 1, 2], target =
3，（方便起见candidates已经排序了）

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

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

此题还需要加一个bool型数组used，用来记录同一树枝上的元素是否使用过。
这个集合去重的重任就是used来完成的。

used[i - 1] == true，说明同一树枝candidates[i - 1]使用过，不用去掉！
used[i - 1] == false，说明同一树层candidates[i - 1]使用过，//就是要对同一树层使用过的元素进行跳过！

一、解法一（使用used数组来去重）

C++代码

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    int sum = 0;
    void backtracing(vector<int>& candidates, int target, int sum, int start, vector<bool>& used){
        // if(sum > target) return;
        if(sum == target){
            res.push_back(path);
            return;
        }
        for(int i = start; i < candidates.size() && sum + candidates[i] <= target; i++){
            if(i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) continue;
            sum += candidates[i];
            path.push_back(candidates[i]);
            used[i] = true;
            cout<<endl;
            backtracing(candidates, target, sum, i + 1, used);
            sum -= candidates[i];
            path.pop_back();
            used[i] = false;     
        }
        return;
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        path.clear();
        res.clear();
        vector<bool>used(candidates.size(), false);
        sort(candidates.begin(), candidates.end());
        backtracing(candidates, target, 0, 0, used);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

二、解法二（使用startIndex来去重）

C++代码

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    int sum = 0;
    void backtracing(vector<int>& candidates, int target, int sum, int startIndex){
        if(sum == target){
            res.push_back(path);
            return;
        }
        for(int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++){
          // 而我们要对同一树层使用过的元素进行跳过
          // 这里使用i > startIndex,之前讲过for循环是在同一树层上进行广度横向遍历
          // 所以当i > startIndex时剪掉的同一树层上需要剪枝的元素
          // 而递归对应在同一树枝进行纵向深度遍历，所以在同一树枝上的i始终等于startIndex
            if(i > startIndex && candidates[i] == candidates[i - 1]) continue;
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracing(candidates, target, sum, i + 1);
            sum -= candidates[i];
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        path.clear();
        res.clear();
        sort(candidates.begin(), candidates.end());
        backtracing(candidates, target, 0, 0);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

总结

**1. 算法思想总结：输入数组candidates有重复元素，输出但还不能有重复的组合这种问题一般方法无法解决时就可以考虑外加一个辅助数组used，用来记录元素是否之前使用过，去重的重任used来完成

也可以使用startIndex来去重，但是不具有通用性，有的问题还是需要使用used数组来解决

所以方法一必须要掌握，方法二有精力可以作为拓展拔高！

2. 关于使不使用startIndex的问题：

startIndex的核心作用是用于去重
因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而77. 组合和216.组合总和III都是是求同一个集合中的组合。

所以当从一个集合中取元素的时候就需要startIndex ，而从两个及以上元素中去元素就不需要startIndex了