Combination Sum Solutions in C++
Number 39
Difficulty Medium
Acceptance 56.2%
Link LeetCode
Other languages Go
Solutions
C++ solution by haoel/leetcode
// Source : https://oj.leetcode.com/problems/combination-sum/// Author : Hao Chen// Date : 2014-07-19#include <iostream>#include <vector>#include <algorithm>using namespace std;void combinationSumHelper(vector<int> &candidates, int start, int target, vector<int> &solution, vector< vector<int> > &result) {if (target<0){return;}if (target==0){result.push_back(solution);return;}for(int i=start; i<candidates.size(); i++){//skip duplicatesif (i>start && candidates[i] == candidates[i-1]) {continue;}solution.push_back(candidates[i]);combinationSumHelper(candidates, i, target - candidates[i], solution, result);solution.pop_back();}}vector<vector<int> > combinationSum(vector<int> &candidates, int target) {vector< vector<int> > result;if (candidates.size()<=0){return result;}sort(candidates.begin(), candidates.end());vector<int> solution;combinationSumHelper(candidates, 0, target, solution, result);return result;}void printMatrix(vector< vector<int> > &vv){for(int i=0; i<vv.size(); i++) {cout << "[";for(int j=0; j<vv[i].size(); j++) {cout << " " << vv[i][j];}cout << "]" << endl;;}}void printArray(vector<int> &v){cout << "{";for(int i=0; i<v.size(); i++) {cout << " " << v[i];}cout << "}" << endl;}int main(int argc, char** argv){int a[] = {4,2,3,3,5,7};vector<int> v(a, a+sizeof(a)/sizeof(int));int target = 7;cout << "array = ";printArray(v);cout << "target = " << target << endl;vector< vector<int> > vv = combinationSum(v, target);printMatrix(vv);return 0;}
C++ solution by pezy/LeetCode
#include <vector>#include <algorithm>using std::vector;class Solution {public:vector<vector<int> > combinationSum(vector<int> &candidates, int target) {vector<vector<int>> ret;std::sort(candidates.begin(), candidates.end());dfs(candidates, target, vector<int>{}, 0, ret);return ret;}void dfs(const vector<int> &cdds, int target, vector<int> curr, size_t index, vector<vector<int>> &ret) {if (!target) {ret.push_back(curr); return; }for (auto i=index; i<cdds.size(); ++i)if (cdds[i] <= target) {curr.push_back(cdds[i]);dfs(cdds, target-cdds[i], curr, i, ret);curr.pop_back();} else break;}};
C++ solution by liuyubobobo/Play-Leetcode
/// Source : https://leetcode.com/problems/combination-sum/description//// Author : liuyubobobo/// Time : 2018-03-04#include <iostream>#include <vector>using namespace std;/// Backtrack/// Time Complexity: O(n^n)/// Space Complexity: O(target)class Solution {public:vector<vector<int>> combinationSum(vector<int> &candidates, int target) {vector<vector<int>> res;vector<int> cur_res;solve(candidates, 0, target, cur_res, res);return res;}private:void solve(const vector<int> &candidates, int index, int target,vector<int>& cur_res, vector<vector<int>>& res){if(target == 0){res.push_back(cur_res);return;}for(int i = index ; i < candidates.size() ; i ++)if(target >= candidates[i]){cur_res.push_back(candidates[i]);solve(candidates, i, target - candidates[i], cur_res, res);cur_res.pop_back();}return;}};void print_vec(const vector<int>& vec){for(int e: vec)cout << e << " ";cout << endl;}int main() {vector<int> candidates = {2, 3, 6, 7};vector<vector<int>> res = Solution().combinationSum(candidates, 7);for(const vector<int>& a_res: res)print_vec(a_res);return 0;}