title: Dynamic programming - canSum memoization in C++
body: <p>The objective is to return true if the <code>sum</code> can be made by adding up elements from a given vector. The vector elements maybe used and reused in any order.</p>
  <p>Example:</p>
  <p>sum = 7, list = [4,5]</p>
  <p>return false because you can't use these list elements to make 7</p>
  <p>sum = 9 or 5 or 20 or 8, list = [4,5]</p>
  <p>return true because 9 = 4+5, 5 is in list already, 20 = 5+5+5+5, 8 = 4 + 4</p>
  <p>I do not know why <code>canSum</code> is not returning anything. When <code>targetSum</code> reaches 0, <code>canSum</code> should return <code>true</code>, and then in <code>memo</code> we <code>emplace</code> (remainder, true). However, the program is not returning anything. Why is that?</p>
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;map&gt;
  
  using namespace std;
  
  
  bool canSum(int targetSum, vector&lt;int&gt; &amp;vec, map&lt;int, bool&gt; &amp;memo) {
      int remainder;
      if (memo[targetSum] == true)
          return true;
      else if (targetSum == 0)
          return true;
      else if (targetSum &lt; 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&lt;int&gt; vector1{7, 14};
      int sum = 300;
      map&lt;int, bool&gt; memo;
      if (canSum(sum, vector1, memo))
          cout &lt;&lt; &quot;true&quot;;
      else
          cout &lt;&lt; &quot;false&quot;;
  }
  </code></pre>