Combination Sum
private:
void backtracking(vector<vector<int>> &results, vector<int> result, vector<int>& candidates, int target, int begin){
for(int i=begin;i<candidates.size();i++){
result.push_back(candidates[i]);
if(target-candidates[i]==0) results.push_back(result);
else if(target-candidates[i]>0) backtracking(results, result, candidates,target-candidates[i], i);
result.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> results;
vector<int> result;
int begin = 0;
backtracking(results, result, candidates,target, begin);
return results;
}
Most basic backtracking. The idea of begin position is excellent, avoid pop operate in vector affect later back tracking.
Backtracking concept: Traverse all possible solution and eliminate unqualified ones at the first place, thus will be faster than brute force.
Combination Sum 2
private:
void backtracking(vector<vector<int>> &results, vector<int> result, vector<int>& candidates, int target, int begin){
for(int i=begin;i<candidates.size();){
result.push_back(candidates[i]);
if(target-candidates[i]==0) results.push_back(result);
else if(target-candidates[i]>0) backtracking(results, result, candidates,target-candidates[i], i+1);
result.pop_back();
int current = candidates[i];
while(i<candidates.size()&&candidates[i]==current){
i++;
}
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
vector<vector<int>> results;
vector<int> result;
int begin = 0;
backtracking(results, result, candidates,target, begin);
return results;
}
Almost the same with Combination Sum1，except that it need to pass same value. How to pass the same value? Take advantage of begin pointer and sort. When the vector is not sorted, it's difficult to judge whether there is same value before, but if it's sorted, then we can easily go through using while loop.
Combination Sum 3
void backtracking(vector<vector<int>> &results, vector<int> result, int k, int n, int begin){
if(k==1){
if(n>=begin&&n<=9) {
result.push_back(n);
results.push_back(result);
}
return;
}
else{
for(int i=begin;i<=10-k&&i<n;i++){
result.push_back(i);
backtracking(results, result, k-1, n-i, i+1);
result.pop_back();
}
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> results;
if(n>45) return results;
vector<int> result;
int begin = 1;
backtracking(results, result,k,n,begin);
return results;
}
Difference is that this one fix number of components, thus we can stop at k-1th value and compare this value with candidates left.
Combination Sum 4
/*
int dp(vector<long long> &result, vector<int>& nums,int target){
cout<<target<<endl;
if(result[target]!=-1) return result[target];
else result[target]=0;
for(int i=0;i<nums.size();i++){
if(target>=nums[i]) result[target]+=dp(result, nums, target-nums[i]);
}
return result[target];
}
int combinationSum4(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
vector<long long> result(target+1,-1);
result[0]=1;
int cur = 0;
dp(result, nums,target);
return result[target];
}
*/
int combinationSum4(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
vector<long long> result(target+1,0);
result[0]=1;
for(int i=1;i<=target;i++){
for(int j=0;j<nums.size();j++)
if(i>=nums[j]) result[i]+=result[i-nums[j]];
}
return result[target];
}
Since it's in fact permutation, backtracking will use a lot of time. How to determine backtracking and dynamic programming - DP uses more space and less time, but it need explicit relationship between different value of input. If the relationship is difficult to find, then DP is more difficult. If the constraint is great, consider use backtracking.
Both bottom-up and Up-bottom can be used in dp. Up-bottom may take useless result but it's more faster. （UP- bottom是树状，每条都会循环直到最底端，所以虽然可以直接利用已经计算过的值，从一个新的root到前一个subtree计算过的底端需要很长时间，好处是可以略过没用的节点。 Bottom-up遍历所有节点但是是线性的，每一个node的值都可以直接计算得出不用生成树状结构，坏处是可能会造成溢出整数ORZ 例如本题的testcase [3, 33, 333] 10000。 java溢出不报错所以java可以pass。 C++里用unsigned int，溢出也不会报错）
Combination Sum 1 DP solution:
private:
void dp(vector<vector<int>> &results, vector<int> result, vector<int>& candidates, int target, int begin){
for(int i=begin;i<candidates.size();i++){
result.push_back(candidates[i]);
if(target-candidates[i]==0) results.push_back(result);
else if(target-candidates[i]>0) dp(results, result, candidates,target-candidates[i], i);
result.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<vector<int>>> ret(target+1,vector<vector<int>>() );
vector<int> result;
for(int xx:candidates){
vector<int> temp;
temp.push_back(xx);
if(target>=xx) ret[xx].push_back(temp);
}
for(int i=1;i<=target;i++){
for(int xx:candidates){
if(i-xx>0&&ret[i-xx].size()!=0){
for(int j=0;j<ret[i-xx].size();j++){
if (ret[i-xx][j][ret[i-xx][j].size()-1]<=xx){
vector<int>temp = ret[i-xx][j];
temp.push_back(xx);
ret[i].push_back(temp);
//cout<<i<<" "<<xx<<endl;
}
}
}
}
}
if(ret[target].size()==0){
vector<vector<int>> results;
return results;
}
return ret[target];
}
Difficulty lies in duplicate is not taken into consideration. Order is useful to avoid as in Combination Sum2. Just add new elements that are no less than last added element, then duplicate can be avoid.
