# A summary of all combination sum problem in LC, C++

• ### Solutions

#### Primitive

test

• try each number and then to the next level with target `chopped off` by the number;
• since we can use the number unlimited times, which means as long as we don't traverse back, it will be okay;
• once the target is equal to zero, we get it and we can collect the `stack`.
``````class Solution {
private:
int size;
void search(vector<int>& candidates, int pos, int target, vector<int>& v, vector<vector<int>>& vv) {
if(target < 0) return;
if(target == 0) { vv.push_back(v); return ; }
for(int i = pos; i < size; ++i) {
v.push_back(candidates[i]);
search(candidates, pos, target-candidates[i], v, vv);
v.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
size = candidates.size();
vector<int> v;
vector<vector<int>> vv;
search(candidates, 0, target, v, vv);
return vv;
}
};
``````

#### Follow-up 1

test

• each number can only be used once, so label the position and move forward one step each time;
• there are only k numbers in a combination, so update the k properly each time;
``````class Solution {
private:
void search(int n, int pos, int k, vector<int>& v, vector<vector<int>>& vv) {
if(n < 0) return ;
if(k == 0) { if(n == 0) vv.push_back(v); return ;}
for(int i = pos; i < 10; ++i) {
v.push_back(i);
search(n-i, i+1, k-1, v, vv);
v.pop_back();
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<int> v;
vector<vector<int>> vv;
search(n, 1, k, v, vv);
return vv;
}
};
``````

#### Follow-up 2

test

• since we can use the number only once, so we have to move forward by one each time;
• to avoid duplicate set, we have to avoid try the same number in the same recursive level;
``````class Solution {
private:
int size;
vector<vector<int>> vv;
void search(vector<int>& candidates, int pos, int target, vector<int>& v, vector<vector<int>>& vv) {
if(target < 0) return;
if(target == 0) { vv.push_back(v); return ; }
for(int i = pos; i < size; ++i) {
if(i==pos || candidates[i]!=candidates[i-1]) {
v.push_back(candidates[i]);
search(candidates, i+1, target-candidates[i], v, vv);
v.pop_back();
}
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
size = candidates.size();
vector<int> v;
search(candidates, 0, target, v);
return vv;
}
};
``````

#### Follow-up 3

test

• recursive backtracking is okay but inefficient, so we have to adopt `Memoization`;
• using map is for better robustness, while an array also does and can be more efficient.
``````class Solution {
private:
unordered_map<int, int> map;
public:
int combinationSum4(vector<int>& nums, int target) {
if(nums.empty() || target<0) return 0;
if(target == 0) return 1;
if(map.count(target)) return map[target];
long count = 0;
for(int i = 0; i < nums.size(); ++i)
count += combinationSum4(nums, target-nums[i]);
return map[target] = count;
}
};
``````
• actually we can do better using DP.
``````class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
int arr[target+1]{1, 0};
for(int i = 1, size = nums.size(); i <= target; ++i)
for(int j = 0; j < size; ++j)
if(i>=nums[j]) arr[i] += arr[i-nums[j]];
return arr[target];
}
};
``````

Always welcome new ideas and `practical` tricks, just leave them in the comments!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.