I am trying to find the best sum with memorization, but when saving the vector pointer inside a map the values keep appending inside the vector and getting the wrong vector. if I commented out the map insertion it works properly. saving nullptr is not possible in case trying to save vector inside the map by reference.
std::vector<int> *bestSumV(int target, int nums[], int size) {
static std::map<int, std::vector<int> *> memo;
if (memo.find(target) != memo.end())
return memo.at(target);
if (target == 0)
return new std::vector<int>();
if (target < 0)
return NULL;
std::vector<int> *bestCom = nullptr;
for (int i = 0; i < size; i++) {
int reminder = target - nums[i];
std::vector<int> *reminderResult = bestSumV(reminder, nums, size);
if (reminderResult != NULL) {
reminderResult->push_back(nums[i]);
if (bestCom == nullptr || reminderResult->size() < bestCom->size()) {
bestCom = static_cast<std::vector<int> *>(reminderResult);
}
}
}
// if i commented out the map insertion i am getting the correct value
// and getting a vector of 5 items
memo.insert(std::make_pair(target, std::move(bestCom)));
return bestCom;
}
void runHowbestTest() {
int testArray[] = {5, 4, 2};
std::vector<int> *bestSum25 = bestSumV(25, testArray, 3);
for (int i = 0; i < bestSum25->size(); i++) {
std::cout << "the items " << bestSum25->at(i) << std::endl;
}
}
Aucun commentaire:
Enregistrer un commentaire