LeetCode第39题之Combination Sum（两种方法）

本文主要是介绍LeetCode第39题之Combination Sum（两种方法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：两种方法都是利用递归回溯，第二方法在第一种方法的基础上对原始数据先进行排序，这样可以剪枝，加快计算速度。第一种方法在LeetCode上测试运行的时间是24ms，第二种方法运行时间为16ms。
方法一：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;class Solution {
private://res保存满足题意的结果vector<vector<int>> res;//保存当前的一种方案vector<int> method;
public:void getCombinationSum(int start, int sum, int target, vector<int> &candidates){//因为canditates经过排序，所以如果sum>targetif (sum > target){return;}//如果满足题意则保存结果else if (sum == target){res.push_back(method);return;} else{for(int i=start;i<candidates.size();++i){//芳第i件物品method.push_back(candidates[i]);getCombinationSum(i, sum+candidates[i], target, candidates);//回溯，去除第i件物品，然后继续放第i+1个数method.pop_back();}}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {int sum = 0;getCombinationSum(0, 0, target, candidates);return res;}
};int main()
{Solution s;vector<int> canditates;canditates.push_back(2);canditates.push_back(7);canditates.push_back(3);canditates.push_back(6);vector<vector<int>> res = s.combinationSum(canditates, 7);//打印结果for (vector<vector<int>>::iterator ita=res.begin();ita!=res.end();++ita){for (vector<int>::iterator itb=ita->begin();itb!=ita->end();++itb){cout<<*itb<<'\t';}cout<<endl;}cout<<endl;return 0;
}

方法二：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;class Solution {
private://res保存满足题意的结果vector<vector<int>> res;//保存当前的一种方案vector<int> method;
public:void getCombinationSum(int start, int sum, int target, vector<int> &candidates){for(int i=start;i<candidates.size();++i){//放第i个数,如果第i个数放进去之后超过了target，则剪枝（直接返回）,因为candidates经过排序，换成后面的数放进去的话肯定也会超过targetif (sum+candidates[i] > target){return;}//如果满足则保存结果else if (sum+candidates[i] == target){method.push_back(candidates[i]);res.push_back(method);method.pop_back();return;}//如果放第i个数后不超过target，则将第i个数放入else{method.push_back(candidates[i]);getCombinationSum(i, sum+candidates[i], target, candidates);//回溯，去除第i个数，然后继续放第i+1个数method.pop_back();}                   }}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {int sum = 0;//排序sort(candidates.begin(), candidates.end());getCombinationSum(0, 0, target, candidates);return res;}
};int main()
{Solution s;vector<int> canditates;canditates.push_back(2);canditates.push_back(7);canditates.push_back(3);canditates.push_back(6);vector<vector<int>> res = s.combinationSum(canditates, 7);for (vector<vector<int>>::iterator ita=res.begin();ita!=res.end();++ita){for (vector<int>::iterator itb=ita->begin();itb!=ita->end();++itb){cout<<*itb<<'\t';}cout<<endl;}cout<<endl;return 0;
}