Combination Sum Solutions in C++

// 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 duplicates
        if (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;
}

#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;
    }
};

/// 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;
}