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是樹狀，每條都會循環(huán)直到最底端，所以雖然可以直接利用已經(jīng)計算過的值，從一個新的root到前一個subtree計算過的底端需要很長時間，好處是可以略過沒用的節(jié)點。 Bottom-up遍歷所有節(jié)點但是是線性的，每一個node的值都可以直接計算得出不用生成樹狀結(jié)構(gòu)，壞處是可能會造成溢出整數(shù)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.
