算法力扣刷题记录六十七【40.组合总和II】

前言

回溯章节第五篇。

记录六十七【40.组合总和II】。

一、题目阅读

给定一个候选人编号的集合 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

二、尝试实现

思路

理解题目：本题的输入数组candidates中有重复的元素，但是每个元素只能使用一次。求组合，组合不能重复。
（弯路） 如果认为candidates中重复元素不影响直接求结果：先对candidates排序，startindex传给下一层时加1，看起来选了每个元素一次。但是组合出现重复。比如以示例2画图，注意不同颜色的“2”：
所以要搜集每个元素出现的次数，并且把candidates去重得到candidate（没有重复元素）的数组。
第一步：搜集每个元素出现的次数——用unordered_map；
第二步：去重得到candidate（没有重复元素）的数组——把unordered_map转换成vector< pair<int ,int>> 类型，pair.first是元素，pair.second是个数。比如示例2这两步之后得到的数组是：
对去重之后的数组candidate求组合。递归函数（回溯操作）开始：

确定递归函数返回值：之前都是用result和temp搜集组合，所以不需要返回值。这里也是。所以void类型；
确定递归函数参数：
- int startindex：指明下一层从candidate哪个下标开始；
- int target和int& sum：一个输入target，一个是当前求和sum。
- result和temp我写到参数里了，可以用全局变量；
- 操作的对象：去重后的数组candidate。
确定终止条件：当sum == target，搜集结果后return。
确定逻辑：
- for循环：从startindex开始，到candidate.size()结束。并且sum < target才继续循环。
- 把元素放入temp，sum做加法，个数减1。
- 当该元素剩余个数 > 0，那么下一层的startindex从i开始；当该元素剩余个数是0，那么下一层的startindex从i+1开始。原因：剩余个数大于0，说明该元素相同的值还有能用的，所以下一层从i开始；剩余个数等于0，说明该元素相同的值没有了，所以下一层从i+1开始；
- 回溯操作：元素弹出temp，sum做减法，个数加1。

代码实现

class Solution {
public:unordered_map<int,int> map;void backtracking(int stratindex,int& sum,int target,vector<int>& temp,vector<vector<int>>& result,vector<pair<int,int>>& candidate){//终止条件if(sum == target){result.push_back(temp);return ;}for(int i = stratindex;i < candidate.size() && sum < target;i++){temp.push_back(candidate[i].first);sum += candidate[i].first;candidate[i].second--;if(candidate[i].second > 0){backtracking(i,sum,target,temp,result,candidate);//startindex是i，递到下一层}else{backtracking(i+1,sum,target,temp,result,candidate);}sum -= candidate[i].first;temp.pop_back();candidate[i].second++;}return;}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<vector<int>> result;vector<int> temp;//中间结果int sum = 0;//统计candidates中每个元素的个数for(int i = 0;i < candidates.size();i++){map[candidates[i]]++;}//去重candidatesvector<pair<int,int>> candidate(map.begin(),map.end());//递归函数backtracking(0,sum,target,temp,result,candidate);return result;}
};

三、参考学习

参考学习链接

学习内容

第一步：先对candidates排序。将所有相同的值放到一起，方便后面的操作。以下都以示例2——candidates = [2,5,2,1,2]为例：
当前操作对象是排序之后的数组：[1,2,2,2,5]。在选择元素，绘制树形结构时：同一层不能选择相同的值，因为在第一个“2”的分支下，后面所有的元素组合已经搜索；到第二个、第三个……“2”的分支时，后面的元素是重复的。所以第一个“2”分支包含了所有。下一个分支应该从“5”开始。

所以这就是参考所讲的“树层去重”但是“树枝不去重”。
用used数组表示candidate数组中某个元素有没有被选到temp中，也就是组合中有没有用到它。
去重逻辑：当该元素和前一个元素相同（同一层），并且前一个元素的used是false（因为i是按顺序增加的，所以前一个是false并且元素值相同说明在第一个“2”就已经搜过了），要continue不处理这个重复分支。
代码实现

class Solution {
public:void backtracking(int stratindex,int& sum,int target,vector<bool> used,vector<int>& temp,vector<vector<int>>& result,vector<int>& candidate){//终止条件if(sum == target){result.push_back(temp);return ;}for(int i = stratindex;i < candidate.size() && sum+candidate[i] <= target;i++){if(i > stratindex && candidate[i] == candidate[i-1] && used[i] == false){//同一层continue;}temp.push_back(candidate[i]);sum += candidate[i];used[i] = true;//使用过//深入下一层，为了每个元素只使用一次，所以startindex是i+1backtracking(i+1,sum,target,used,temp,result,candidate);sum -= candidate[i];temp.pop_back();used[i] = false;//回归没使用状态}return;}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<vector<int>> result;vector<int> temp;//中间结果vector<bool> used(candidates.size(),false);//初始化都没有用过int sum = 0;//排序把相同元素放到一起sort(candidates.begin(),candidates.end());//递归函数backtracking(0,sum,target,used,temp,result,candidates);return result;}
};