mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
58 lines
3.2 KiB
Markdown
58 lines
3.2 KiB
Markdown
# [40. Combination Sum II](https://leetcode.com/problems/combination-sum-ii/)
|
||
# 思路
|
||
题意：从一个数组candidates（允许存在重复元素）里面选一些数字出来，使这些数字的和恰好为target，candidates里的数只能使用一次。可见这题与[39. Combination Sum](https://leetcode.com/problems/combination-sum/)有两个不同点：
|
||
1. 在挑选数字出来时，candidates里的数只能使用一次；
|
||
2. candidates里的元素允许重复；
|
||
|
||
上面两个不同点也对应于代码中两个不同点（见下面的代码）。
|
||
|
||
思路其实和39题类似的，建议先去看看我写的[39题题解](https://github.com/ShusenTang/LeetCode/blob/master/solutions/39.%20Combination%20Sum.md)。
|
||
仍然是一个回溯题（类似DFS），为了避免得到重复结果，先对数组进行排序（常规操作）。
|
||
为了进行递归调用，我们定义了一个函数helper，传入的参数有
|
||
* nums - 当前被选中的数
|
||
* candidates - 就是题意里面的数组（从小到大排序好的）
|
||
* start - 只能考虑数组candidates下标为start及后面的数
|
||
* curr_target - 当前的目标（我们希望的就是nums的元素和加上curr_target就等于target）
|
||
|
||
helper函数定义如下：
|
||
* 当`curr_target == 0`时，说明nums的元素和就等于target，nums就是一组我们要求的数，push进结果数组即可。
|
||
* 当`start >= candidates.size()`时，说明start已经超过了candidates最大下标，返回即可；
|
||
* 当`candidates[start] > curr_target`时，说明candidates中（当前可用的）最小的数都比curr_target大，也是直接返回。
|
||
|
||
--------------上面都和39题一样的，只是下面有两个不同点---------------
|
||
* 前面三个条件都不满足时，假设`k = candidates[start]`就有两条路要走:
|
||
1. 将k加入到nums中，令`curr_target = curr_target - k`且`start = start+1`, 进入下一层递归；
|
||
2. 不将k加入到nums中, 由于candidates里的元素允许重复，所以candidates[start+1]也就可能等于k，所以我们应该让start移动到最后一个k所在位置，再令`start + 1`进入下一层递归；
|
||
|
||
# C++
|
||
``` C++
|
||
class Solution {
|
||
private:
|
||
vector<vector<int>>res;
|
||
void helper(vector<int>& nums, const vector<int>& candidates, int start, const int& curr_target){
|
||
if(curr_target == 0){
|
||
res.push_back(nums);
|
||
return;
|
||
}
|
||
if(start >= candidates.size() || candidates[start] > curr_target) return;
|
||
|
||
nums.push_back(candidates[start]);
|
||
helper(nums, candidates, start + 1, curr_target - candidates[start]); // 不同点一，39传入的是start，因为39允许多次使用candidates里的数
|
||
nums.pop_back();
|
||
// 不同点二，因为candidates里的元素允许重复，所以要跳过这些重复元素
|
||
while(start < candidates.size() - 1 && candidates[start] == candidates[start+1])
|
||
start++;
|
||
helper(nums, candidates, start + 1 , curr_target);
|
||
return;
|
||
}
|
||
public:
|
||
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
|
||
if(candidates.empty()) return res;
|
||
sort(candidates.begin(), candidates.end());
|
||
vector<int>nums;
|
||
helper(nums, candidates, 0, target);
|
||
return res;
|
||
}
|
||
};
|
||
```
|