# DP solution

• althought it seems stupid using dp, since it seems hard to get the set from the result..but, I finish it cost several hours(it due to my IQ)..Maybe it will be needed for some others..

``````vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
int n = candidates.size(), start = 0;
vector<vector<int>> dp(n + 1);
for (int i = 0; i <= n; i++)
dp[i] = vector<int>(target + 1, 0);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= target; j++)
{
dp[i][j] = dp[i - 1][j];
if ((j - candidates[i - 1])>0)
dp[i][j] = dp[i - 1][j] + dp[i][j - candidates[i - 1]];
if (j == candidates[i - 1])
dp[i][j]++;
}
}
vector<vector<int>> res(dp[n][target]);
fun(res, dp, candidates, n, start, target);
return res;

}
void fun(vector<vector<int>> &res, vector<vector<int>> &dp, vector<int> &candidates, int i, int &start, int target)
{
if (i <= 0 || target <= 0)
return;
if (candidates[i - 1] == target)
res[start++].push_back(candidates[i - 1]);
if ((target - candidates[i - 1]) >= 0 && dp[i][target - candidates[i - 1]])
{
for (int j = start; j < dp[i][target - candidates[i - 1]] + start; j++)
res[j].push_back(candidates[i - 1]);
fun(res, dp, candidates, i, start, target - candidates[i - 1]);
}
if (dp[i - 1][target])
fun(res, dp, candidates, i - 1, start, target);
}
``````

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