LeetCode 0039 - Combination Sum
# Hints
- DFS
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a set of candidate numbers candidates
(without duplicates) and a target number target
, find all unique combinations in candidates
where the candidate numbers sums to target
.
The same repeated number may be chosen from candidates
unlimited number of times.
Note:
All numbers (including
target
) will be positive integers.The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
# 题意
给定一个长为 的正整数数组 candidates
,数组中不含重复元素。给定一个整数 target
,要求从 candidates
中选择若干个数,其和恰好为 target
。每个数可以选择任意多次,要求求出所有的合法选数方案。
# 题解
直接 DFS 暴力枚举所有方案即可。
可以进行一个简单的剪枝。我们先将数组升序排序,然后依次枚举每个数的选择次数。设 为当前枚举到的数的下标,当已选数之和 满足 时,说明无论接下来如何选都会导致总和超过 target
,可停止当前支路的搜索。
# AC代码
class Solution {
public:
vector<vector<int>> combinationSum(vector<int> & candidates, int target) {
// 排序
sort(candidates.begin(), candidates.end());
// DFS
vector<vector<int>> res;
vector<int> vec;
dfs(0, target, vec, res, candidates);
// 返回
return res;
}
// 深度优先搜索
void dfs(int index, int target, vector<int> & vec, vector<vector<int>> & res, const vector<int> & candidates) {
// 递归终止
if (target == 0) {
res.push_back(vec);
return;
}
if (index == candidates.size()) {
return;
}
// 剪枝
if (target < candidates[index]) {
return;
}
// 递归
int m = target / candidates[index];
for (int i = 0; i <= m; i ++) {
dfs(index + 1, target - i * candidates[index], vec, res, candidates);
vec.push_back(candidates[index]);
}
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