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]); } } } } };