题目描述
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
样例
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
算法1
(DFS) $O(2^n)$
blablabla
时间复杂度
参考文献
C++ 代码
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
std::sort(candidates.begin(), candidates.end());
vector<vector<int>> answer;
vector<int> intermediate;
dfs(candidates, target, 0, intermediate, answer);
return answer;
}
void dfs (
const vector<int>& candidates,
int target, int start,
vector<int>& intermediate,
vector<vector<int>> & answer
) {
if (target == 0) {
answer.push_back(intermediate);
return;
}
for (int i = start; i < candidates.size(); ++i) {
if (target - candidates[i] >= 0) {
intermediate.push_back(candidates[i]);
dfs(candidates, target - candidates[i], i, intermediate, answer);
intermediate.pop_back();
}
}
}
};