Combination Sum II Solutions in C++

// Source : https://oj.leetcode.com/problems/combination-sum-ii/
// 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
        int n = candidates[i];
        if (i>start && candidates[i] == candidates[i-1]) {
            continue;
        }
        solution.push_back(n);
        combinationSumHelper(candidates, i+1, target - n, solution, result);
        solution.pop_back();
    }
}

vector<vector<int> > combinationSum2(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;
}

void test(int a[], int len, int target)
{
    vector<int> v(a, a+len);
    cout << "array  = ";
    printArray(v);
    cout << "target = " << target << endl;

    vector< vector<int> > vv = combinationSum2(v, target);
    printMatrix(vv);
}

int main(int argc, char** argv)
{
    #define TEST(a, t) test(a, sizeof(a)/sizeof(int), target)
    int a[] = {4,2,3,3,5,7};
    int target = 7;
    TEST(a, target);

    int b[] = {10,1,2,7,6,1,5};
    target = 8;
    TEST(b, target);

    int c[] = {2,2,2};
    target = 2;
    TEST(c, target);

    return 0;
}

#include <vector>
#include <set>
using std::vector;
#include <algorithm>
#include <functional>

class Solution {
public:
    void dfs(const vector<int> &num, vector<vector<int>> &ret, int target, vector<int> cur, size_t start) {
        if (target == 0) { ret.push_back(cur); return; }
        for (auto i = start; i < num.size(); ++i)
            if (i > start && num[i] == num[i-1]) continue;
            else if (num.at(i) <= target) {
                cur.push_back(num.at(i));
                dfs(num, ret, target - num.at(i), cur, i+1);
                cur.pop_back();
            } else break;
    }

    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        vector<vector<int>> ret;
        std::sort(num.begin(), num.end());
        dfs(num, ret, target, vector<int>{}, 0);
        return ret;
    }
};

/// Source : https://leetcode.com/problems/combination-sum-ii/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>> combinationSum2(vector<int>& candidates, int target) {

        sort(candidates.begin(), candidates.end());

        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(i > index && candidates[i] == candidates[i-1])
                continue;
            if(target >= candidates[i]){
                cur_res.push_back(candidates[i]);
                solve(candidates, i + 1, 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 = {10, 1, 2, 7, 6, 1, 5};
    vector<vector<int>> res = Solution().combinationSum2(candidates, 8);
    for(const vector<int>& a_res: res)
        print_vec(a_res);

    return 0;
}