上海网站建设知识 博客,网站建设数据库的购买,html和php做网站哪个好,滨州网站建设开发公司文章目录 回溯7. 组合总和8. 组合总和 II 回溯
7. 组合总和
39. 组合总和 思路#xff1a; 基本的递归回溯#xff0c;只不过这里递归树每层的起始索引位置变成了 i #xff0c;而不是下一个元素的索引 i1#xff0c;因为可以重复选择。 复杂度#xff1a; O ( n 2 n ) … 文章目录 回溯7. 组合总和8. 组合总和 II 回溯
7. 组合总和
39. 组合总和 思路 基本的递归回溯只不过这里递归树每层的起始索引位置变成了 i 而不是下一个元素的索引 i1因为可以重复选择。 复杂度 O ( n 2 n ) O(n2^n) O(n2n) 每个数字都有是否被选择两种可能 2 n 2^n 2n递归树的最大深度是 target / min(candidates) n n n. class Solution {
public:vectorvectorint combinationSum(vectorint candidates, int target) {vectorint tmp;sort(candidates.begin(), candidates.end()); // 对 candidates 升序排列方便后续剪枝backward(tmp, 0, candidates, target);return ans;}private:vectorvectorint ans;void backward(vectorint tmp, int start, vectorint candidates, int target) {if (target 0) {ans.push_back(tmp);return ;}for (int i start; i candidates.size(); i) {if (target candidates[i]) break; // 剪枝tmp.push_back(candidates[i]);backward(tmp, i, candidates, target - candidates[i]);tmp.pop_back();}}
};8. 组合总和 II
40. 组合总和 II 思路 这一题上一题的区别是多了不能重复的限制。 如下图我们可以看出重复的是蓝色的同一层的部分而在棕色的分支处的重复数字不会引起结果的重复。 所以剪枝只需要剪掉同一层相同元素搜索得到的答案。即用 if (i start candidates[i] candidates[i - 1]) continue; 将蓝色部分进行剪枝。 class Solution {
public:vectorvectorint combinationSum2(vectorint candidates, int target) {vectorint tmp;sort(candidates.begin(), candidates.end());backward(tmp, 0, candidates, target);return ans;}private:vectorvectorint ans;void backward(vectorint tmp, int start, vectorint candidates, int target) {if (target 0) {ans.push_back(tmp);return ;}for (int i start; i candidates.size(); i) {// 剪枝if (target candidates[i]) break;// 去重if (i start candidates[i] candidates[i - 1]) continue;tmp.push_back(candidates[i]);backward(tmp, i 1, candidates, target - candidates[i]);tmp.pop_back();}}
};
