【算法与数据结构】39、LeetCode组合总和

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

二、解法

  思路分析：这道题当中数字可以多次使用，那么我们在递归语句当中不能直接找下一个candidate的元素，需要不断累加重复元素，直到它>=target，才能进入下一个循环，同时需要做剪枝优化，循环只在这个条件下进行sum+candidates[i] <= target。这道题的框架基于【算法与数据结构】216、LeetCode组合总和 III修改。

  程序如下：

class Solution {
private:vector<vector<int>> result;     // 结果合集vector<int> path;void backtracking(const vector<int>& 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() && sum+candidates[i] <= target; i++) { // 剪枝优化sum += candidates[i];path.push_back(candidates[i]);  // 处理节点backtracking(candidates, target, sum, i);  // 递归sum -= candidates[i];path.pop_back();    // 回溯，撤销处理的节点}}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<int> nums = candidates;		// 对candidates数组升排序sort(nums.begin(), nums.end());backtracking(nums, target, 0, 0);return result;}
};

复杂度分析：

• 时间复杂度： $O(n\ast 2^n)$。
• 空间复杂度：$O(target)$。

三、完整代码

# include <iostream>
# include <string>
# include <vector>
# include <algorithm>
using namespace std;class Solution {
private:vector<vector<int>> result;     // 结果合集vector<int> path;void backtracking(const vector<int>& 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() && sum+candidates[i] <= target; i++) { // 剪枝优化sum += candidates[i];path.push_back(candidates[i]);  // 处理节点backtracking(candidates, target, sum, i);  // 递归sum -= candidates[i];path.pop_back();    // 回溯，撤销处理的节点}}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<int> nums = candidates;		// 对candidates数组升排序sort(nums.begin(), nums.end());backtracking(nums, target, 0, 0);return result;}
};int main() {vector<int> candidates = { 2, 3, 6, 7 };int target = 7;Solution s1;vector<vector<int>> result = s1.combinationSum(candidates, target);for (vector<vector<int>>::iterator it = result.begin(); it != result.end(); it++) {for (vector<int>::iterator jt = (*it).begin(); jt != (*it).end(); jt++) {cout << *jt << " ";}cout << endl;}system("pause");return 0; 
}

end