# DP based solution - Generate solution for k number using solutions from (k-1) numbers bottom up

• DP solution -
We generate sub results for k-1 numbers and target value from 1 to target and then use that to generate results for k numbers

``````
vector<vector<int>> combinations(int target, int k) {

vector<vector<vector<int>>>* localResultKMinus1 = new vector<vector<vector<int>>>(target+1);
vector<vector<vector<int>>>* localResultK = new vector<vector<vector<int>>>(target+1);
vector<vector<vector<int>>>* temp;

for(int i=1; i<=target;i++) {
localResultKMinus1->at(i) = {};
}

int cnt = 1;

while(cnt <= k) {
// clean up for the current run
for(int i=1; i<=target;i++) {
localResultK->at(i) = {};
}

for(int i=1;i<=target;i++) {
for(int numIndex = 1; numIndex <= 9;numIndex++) {
if(numIndex > i) break;
vector<int> singleNum = {numIndex};
if (numIndex == i && cnt == 1) localResultK->at(i).push_back(singleNum);

vector<vector<int>> prevResult = localResultKMinus1->at(i-numIndex);
for(auto p = prevResult.begin(); p != prevResult.end(); p++) {
if(numIndex > (*p).back()) {
p->push_back(numIndex);
localResultK->at(i).push_back(*p);
}
}
}
}

temp = localResultKMinus1;
localResultKMinus1 = localResultK;
localResultK = temp;
cnt++;
}

return localResultKMinus1->at(target);
}

``````

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