网站制作学校要的,云南网站备案难吗,广东省公共资源交易中心地址,搜索广告优化文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析#xff1a;这道题当中数字可以多次使用#xff0c;那么我们在递归语句当中不能直接找下一个candidate的元素可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析这道题当中数字可以多次使用那么我们在递归语句当中不能直接找下一个candidate的元素需要不断累加重复元素直到它target才能进入下一个循环同时需要做剪枝优化循环只在这个条件下进行sumcandidates[i] target。这道题的框架基于【算法与数据结构】216、LeetCode组合总和 III修改。 程序如下
class Solution {
private:vectorvectorint result; // 结果合集vectorint path;void backtracking(const vectorint candidates, const int target, int sum, int startIndex) {if (sum target) return; // 剪枝if (sum target) {result.push_back(path);return;}for (int i startIndex; i candidates.size() sumcandidates[i] target; i) { // 剪枝优化sum candidates[i];path.push_back(candidates[i]); // 处理节点backtracking(candidates, target, sum, i); // 递归sum - candidates[i];path.pop_back(); // 回溯撤销处理的节点}}
public:vectorvectorint combinationSum(vectorint candidates, int target) {vectorint nums candidates; // 对candidates数组升排序sort(nums.begin(), nums.end());backtracking(nums, target, 0, 0);return result;}
};复杂度分析
时间复杂度 O ( n ∗ 2 n ) O(n*2^n) O(n∗2n)。空间复杂度 O ( t a r g e t ) O(target) O(target)。
三、完整代码
# include iostream
# include string
# include vector
# include algorithm
using namespace std;class Solution {
private:vectorvectorint result; // 结果合集vectorint path;void backtracking(const vectorint candidates, const int target, int sum, int startIndex) {if (sum target) return; // 剪枝if (sum target) {result.push_back(path);return;}for (int i startIndex; i candidates.size() sumcandidates[i] target; i) { // 剪枝优化sum candidates[i];path.push_back(candidates[i]); // 处理节点backtracking(candidates, target, sum, i); // 递归sum - candidates[i];path.pop_back(); // 回溯撤销处理的节点}}
public:vectorvectorint combinationSum(vectorint candidates, int target) {vectorint nums candidates; // 对candidates数组升排序sort(nums.begin(), nums.end());backtracking(nums, target, 0, 0);return result;}
};int main() {vectorint candidates { 2, 3, 6, 7 };int target 7;Solution s1;vectorvectorint result s1.combinationSum(candidates, target);for (vectorvectorint::iterator it result.begin(); it ! result.end(); it) {for (vectorint::iterator jt (*it).begin(); jt ! (*it).end(); jt) {cout *jt ;}cout endl;}system(pause);return 0;
}end
