40. 组合总和 II - 力扣（LeetCode）

发表于 更新于 分类于 阅读次数： Disqus：

题目描述

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

题解

此题与“组合之和”一题有两个不同：一是该题数组中的数字可能会重复；二是每个数字在每个组合中只能使用一次。 数字重复带来的一个问题是组合可能会重复，所以需要做去重处理。 同“组合之和”一题一样，这里使用的也是递归+剪枝，这里首先对数据进行排序，方便剪枝和去重。 每个数字只能使用一次，可以修改递归的起点，之前是i，这里可以修改为i + 1。 其它细节具体见代码。

代码

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
class Solution {
public:
    vector<vector<int>> res;
    vector<int>sol;
    void dfs(vector<int>& nums, int beg, int target){//递归
        for(int i = beg; i < nums.size(); ++i){
            if(target - nums[i] < 0){//之和大于则直接return
                return;
            }
            if(i > beg && nums[i] == nums[i - 1]){//去重
                continue;
            }
            sol.push_back(nums[i]);
            if(target == nums[i]){//满足条件 放到题解中
                res.push_back(sol);
                sol.pop_back();
                return;
            }
            else{
                dfs(nums, i + 1, target - nums[i]);//之和小于target，则继续向下递归，注意此时beg是从i+1开始的
                sol.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates, 0, target);
        return res;
    }
};

运行结果