Leetcode: Combination Sum

Description:
Given a set of candidates(C), and a target(T). find all unique combinations in C where they sums to T.

Analysis:
Basically, there is no solution other than computing all possible combinations out of C. Also, optimization is pretty limited. My solutions all have dependency on T.

Solution 1: Divide and Conquer/DFS

The subproblem is defined as the function Kernel(curset, candidates, target). @Curset is one of combinations who sum up to T – @target. It is done by caller(upper) function. Kernel is to compute all combinations who sum up to @target using @candidates, and then append them to @curset. Therefore, a completed @curset is one of  combinations that sum up to T.

class Solution {
 typedef vector<vector<int> > VVec;
 VVec res;
public:
 vector<vector<int> > combinationSum(vector<int> &candidates, int target)
 {
 res.clear(); // leetcode runs all tests using same Solution instance.
 sort(candidates.begin(), candidates.end(), greater<int>());
 Kernel(vector<int>(), 0, candidates, target);
 return res;
 }

 void Kernel(vector<int> curset,int idx_cand, const vector<int> &candidates, int target)
 {
 if (idx_cand >= candidates.size())
 return;

 int val = candidates[idx_cand];
 Kernel(curset, idx_cand + 1, candidates, target);
 if (target == val)
 {
 curset.push_back(val);
 reverse(curset.begin(), curset.end());
 res.push_back(curset);
 }

 else if (target > val)
 {
 curset.push_back(val);
 Kernel(curset, idx_cand, candidates, target - val);
 }
 }
}

Solution 2: DP

This algorithm maintains all combination sums of a current candidate set(CCS). CCS is extended by incremental insertion. Insertion is done at 2 steps: 1) insert a new sum and 2) extend current sumset. Notice that the insertion works only if each candidate can be applied repeatedly.

#include <algorithm>
using namespace std;

class Solution {
 typedef vector<int> Comb;
 typedef vector<Comb> Combs;
 vector<Combs> sums_;
 int max_sum_;
public:
 vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
 Init(target);
 for (int i = 0; i < candidates.size(); i++)
 {
 InsertCandidate(candidates[i]);
 }

 for (int i = 0; i < sums_[target].size(); i++)
 sort(sums_[target][i].begin(), sums_[target][i].end());
 return sums_[target];
 }

 void Init(int maxsum)
 {
 max_sum_ = maxsum;
 sums_.clear();
 sums_.resize(maxsum + 10); // 10 edge size.
 }

 void InsertCandidate(int val)
 {
 // 1. insert new sum
 if (val <= max_sum_)
 {
 Comb comb;
 comb.push_back(val);
 sums_[val].push_back(comb);
 }

 // 2. extend current sumset
 for (int s = 0; s <= max_sum_; s++)
 {
 if (s + val > max_sum_)
 break;

 if (sums_[s].size())
 {
 Combs combs = sums_[s];
 for (int k =0; k < combs.size(); k++)
 {
 combs[k].push_back(val);
 sums_[s+val].push_back(combs[k]);
 }
 }
 }

 }

};

Solution 3:

#include <algorithm>
#include <map>
using namespace std;

class Solution {
 typedef vector<int> Comb;
 typedef vector<Comb> Combs;
 typedef map<int, Combs> Map;
 Map sums_;
 int max_sum_;
public:
 vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
 Init(target);
 for (int i = 0; i < candidates.size(); i++)
 {
 InsertCandidate(candidates[i]);
 }

for (int i = 0; i < sums_[target].size(); i++)
 sort(sums_[target][i].begin(), sums_[target][i].end());
 return sums_[target];
 }

void Init(int maxsum)
 {
 max_sum_ = maxsum;
 sums_.clear();
 //sums_.resize(maxsum + 10); // 10 edge size.
 }

void InsertCandidate(int val)
 {
 // 1. insert new sum
 if (val <= max_sum_)
 {
 Comb comb;
 comb.push_back(val);
 sums_[val].push_back(comb);
 }

// 2. extend current sumset
 //for (int s = 0; s <= max_sum_; s++)
 for (Map::iterator it = sums_.begin();
 it != sums_.end();
 it ++)
 {
 int s = it->first;
 if (s + val > max_sum_)
 break;

if (sums_[s].size())
 {
 Combs combs = sums_[s];
 for (int k =0; k < combs.size(); k++)
 {
 combs[k].push_back(val);
 sums_[s+val].push_back(combs[k]);
 }
 }
 }

}

};