# Dynamic Programming Solution

• It adapts the DP solution of coin change problem

``````class Solution {
public:
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
vector< vector< vector<int> > > combinations(target + 1, vector<vector<int>>());
combinations[0].push_back(vector<int>());
for (auto& score : candidates)
for (int j = score; j <= target; j++)
if (combinations[j - score].size() > 0)	{
auto tmp = combinations[j - score];
for (auto& s : tmp)
s.push_back(score);
combinations[j].insert(combinations[j].end(), tmp.begin(), tmp.end());
}
auto ret = combinations[target];
for (int i = 0; i < ret.size(); i++)
sort(ret[i].begin(), ret[i].end());
return ret;
}
};``````

• Can you elaborate your idea ?

• This post is deleted!

• Hnn, I use the same idea as you did. I can help illustrate the idea.

Thinking about there is an opt[] array, each element in the array is a vector<vector<int>>.
We do DP from opt[0] to opt[target].

// base case

opt[0] = [[]]

// iteration

opt[i] =

1. add candidates[j] to each list in opt[i-candidates[j]] if i > candidates[j]
.Add each list to opt[i]

2. create candidates[j] as a new vector<int> if i == candidates[j]
.Add this list to opt[i]

• This is just like a coin change/knapsack problem. We need to create a vector of the size of target. and for each o(1)...o(target) we get the values. and if in between we find any sum == target, add that into the result

• Sorting input first is easier

``````vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
sort(candidates.begin(), candidates.end());
vector< vector< vector<int> > > combinations(target + 1, vector<vector<int>>());
combinations[0].push_back(vector<int>());
for (auto& score : candidates)
for (int j = score; j <= target; j++){
auto sls = combinations[j - score];
if (sls.size() > 0) {
for (auto& s : sls)
s.push_back(score);
combinations[j].insert(combinations[j].end(), sls.begin(), sls.end());
}
}
return combinations[target];
}
``````

• How do you avoid duplicates in this case? For example, how do you differentiate from
[1, 2, 2, 3] and [2, 1, 2, 3]?

• Let me help illustrate the idea.

We consider, what targets will be yielded, every time a candidate is appended to all the existing combinations.

Here is my more understandable code using the same idea.

``````vector<vector<int>> Solution::combinationSum_dp_increment(vector<int> &candidates, int target) {
sort(candidates.begin(), candidates.end());

vector<vector<vector<int>>> dp(target + 1, vector<vector<int>>());
dp[0].push_back(vector<int>());

for (const int &candidate : candidates) {
// all the existing combinations, except for those whose sum exceeds target
for (int sub_target = 0; sub_target + candidate <= target; ++sub_target){
vector<vector<int>> new_combinations = dp[sub_target];
for (vector<int> &new_combination: new_combinations) {  // append a candidate
new_combination.push_back(candidate);
}
int target_yielded = sub_target + candidate;  // the target yielded
dp[target_yielded].insert(dp[target_yielded].end(), new_combinations.begin(), new_combinations.end());
}
}

return dp[target];
}
``````

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