Dynamic programming - canSum memoization in C++

Question

The objective is to return true if the sum can be made by adding up elements from a given vector. The vector elements maybe used and reused in any order.

Example:

sum = 7, list = [4,5]

return false because you can't use these list elements to make 7

sum = 9 or 5 or 20 or 8, list = [4,5]

return true because 9 = 4+5, 5 is in list already, 20 = 5+5+5+5, 8 = 4 + 4

I do not know why canSum is not returning anything. When targetSum reaches 0, canSum should return true, and then in memo we emplace (remainder, true). However, the program is not returning anything. Why is that?

#include <iostream>
#include <vector>
#include <map>

using namespace std;


bool canSum(int targetSum, vector<int> &vec, map<int, bool> &memo) {
    int remainder;
    if (memo[targetSum] == true)
        return true;
    else if (targetSum == 0)
        return true;
    else if (targetSum < 0)
        return false;
    else
        for (auto i : vec) {
            remainder = targetSum - i;
            if (canSum(remainder, vec, memo)) {
                memo.emplace(remainder, true);
                return true;
            }
        }
    memo.emplace(remainder, false);
    return false;
}

int main() {
    vector<int> vector1{7, 14};
    int sum = 300;
    map<int, bool> memo;
    if (canSum(sum, vector1, memo))
        cout << "true";
    else
        cout << "false";
}

Answer 1

The problem in your code is the way you handle the storing of sates in your memo table. You store only when the result is desired in the for loop and same problem is while returning using the memo table. So, the states which result in false are not stored in your memo until the complete recursive call ends and you are out of the loop. So, your recursion keeps on calculating the same states again and again. Your logic is correct but dynamic programming integration in recursive code is not proper. Your code will give an output, you just need to wait for a long time even for a small input. Below I have explained the above mentioned problems in detail.

1. You return from memo only if the result is true i.e. the if condition:

   ...
   if(memo[remainder] == true)
       return true;
   ...
   

   is the problem. We use dynamic programming to save the result of a state that has been calculated so that if we come across the same problem in future, we don't have to recalculate it and we can return its result from saved memo table to avoid going into recursion again. We return the result from memo table irrespective of the result. But here you are returning only if the result was true. You should instead use this:

   ...
   if (memo.find(targetSum)!=memo.end())
       return memo[targetSum];
   ...
   

2. This is also the problem while you are storing the results in the memo table in the for loop. The if condition in the for loop:

   for (auto i : vec) {
       remainder = targetSum - i;
       if (canSum(remainder, vec, memo)) {
           memo.emplace(remainder, true);
           return true;
       }
   }
   

   is the problem. We store the result in the memo table irrespective of our desired result.

Here is the complete code with both problems fixed.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

bool canSum(int targetSum, vector<int> &vec, map<int, bool> &memo) {
    int remainder;
    if (memo.find(targetSum)!=memo.end())
        return memo[targetSum];
    else if (targetSum == 0)
        return true;
    else if (targetSum < 0)
        return false;
    else{
        bool ans = false;
        for (auto i : vec) {
            remainder = targetSum - i;
            ans = ans || canSum(remainder, vec, memo);
            if (ans) {
                memo.emplace(targetSum, true);
                return true;
            }
        }
        memo.emplace(targetSum, false);
    }
    return false;
}

int main() {
    vector<int> vector1{7, 14};
    int sum = 300;
    map<int, bool> memo;
    if (canSum(sum, vector1, memo))
        cout << "true";
    else
        cout << "false";
}

This is the answer to your question "I do not know why canSum is not returning anything."

Now, in general one should not use recursive DP as it is too much time consuming and iterative DP is best suited for competitive programming problems.