LeetCode 0040 - Combination Sum II
# Hints
- DFS
# 前置题目
LeetCode 0039 - Combination Sum
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a collection of candidate numbers and a target number , find all unique combinations in where the candidate numbers sums to .
Each number in may only be used once in the combination.
Note:
All numbers (including ) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]
# 题意
给定一个长为 的正整数数组 ,给定一个整数 ,要求从 中选择若干个数,其和恰好为 。每个数至多可选择一次,要求求出所有的合法选数方案。
# 题解
本题是LeetCode 0039的简单变形,只需在DFS之前预处理一下,统计每种数的出现次数,并在DFS时限制选取次数即可。
# AC代码
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int> & candidates, int target) {
// 特判
if (candidates.empty()) {
return vector<vector<int>>();
}
// 排序
sort(candidates.begin(), candidates.end());
// 计数
vector<pair<int, int>> nctes;
int val = candidates[0], cnt = 1;
for (int i = 1; i < candidates.size(); i ++) {
if (val != candidates[i]) {
nctes.push_back(pair<int, int>(val, cnt));
val = candidates[i];
cnt = 1;
} else {
cnt ++;
}
}
nctes.push_back(pair<int, int>(val, cnt));
// DFS
vector<vector<int>> res;
vector<int> vec;
dfs(0, target, vec, res, nctes);
// 返回
return res;
}
// 深度优先搜索
void dfs(int index, int target, vector<int> & vec, vector<vector<int>> & res, const vector<pair<int, int>> & candidates) {
// 递归终止
if (target == 0) {
res.push_back(vec);
return;
}
if (index == candidates.size()) {
return;
}
// 剪枝
if (target < candidates[index].first) {
return;
}
// 递归
int m = candidates[index].second;
for (int i = 0; i <= m; i ++) {
dfs(index + 1, target - i * candidates[index].first, vec, res, candidates);
vec.push_back(candidates[index].first);
}
for (int i = 0; i <= m; i ++) {
vec.pop_back();
}
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01