Алгоритм изменения монет DP Распечатать все комбинации

Классическая проблема обмена монет хорошо описана здесь: http://www.algorithmist.com/index.php/Coin_Change

Здесь я хочу не только узнать, сколько существует комбинаций, но и распечатать их все. Я использую тот же алгоритм DP в этой ссылке в моей реализации, но вместо записи, сколько комбинаций в таблице DP для DP[i][j] = countЯ храню комбинации в таблице. Поэтому я использую трехмерный вектор для этой таблицы DP.

Я попытался улучшить свою реализацию, заметив, что при поиске таблицы требуется только информация из последней строки, поэтому мне не нужно всегда хранить всю таблицу.

Однако мое улучшенное решение DP все еще кажется довольно медленным, поэтому мне интересно, есть ли какая-то проблема в моей реализации ниже или может быть больше оптимизации. Спасибо!

Вы можете запустить код напрямую:

#include <iostream>
#include <stdlib.h>
#include <iomanip>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {

int total = 10; //total amount
//available coin values, always include 0 coin value
vector<int> values = {0, 5, 2, 1};
sort(values.begin(), values.end()); //I want smaller coins used first in the result

vector<vector<vector<int>>> empty(total+1); //just for clearing purpose
vector<vector<vector<int>>> lastRow(total+1);
vector<vector<vector<int>>> curRow(total+1);for(int i=0; i<values.size(); i++) {for(int curSum=0; curSum<=total; curSum++){
if(curSum==0) {
//there's one combination using no coins
curRow[curSum].push_back(vector<int> {});

}else if(i==0) {
//zero combination because can't use coin with value zero

}else if(values[i]>curSum){
//can't use current coin cause it's too big,
//so total combination for current sum is the same without using it
curRow[curSum] = lastRow[curSum];

}else{
//not using current coin
curRow[curSum] = lastRow[curSum];
vector<vector<int>> useCurCoin = curRow[curSum-values[i]];

//using current coin
for(int k=0; k<useCurCoin.size(); k++){

useCurCoin[k].push_back(values[i]);
curRow[curSum].push_back(useCurCoin[k]);
}
}
}

lastRow = curRow;
curRow = empty;
}

cout<<"Total number of combinations: "<<lastRow.back().size()<<endl;
for (int i=0; i<lastRow.back().size(); i++) {
for (int j=0; j<lastRow.back()[i].size(); j++) {
if(j!=0)
cout<<" ";
cout<<lastRow.back()[i][j];
}
cout<<endl;
}
return 0;
}