title: How to add memoization to coin change
body: <p>I am looking at the Leetcode <a href="https://leetcode.com/problems/coin-change/description/" rel="nofollow noreferrer">problem</a> of coin change. I came up with a brute force solution and have some ideas on how to add memoization but looks like I am missing something. Below is my non-memoized function that works. </p>
  
  <p>I was initially thinking about creating a hashmap that stores a tuple of vector, index, and sum and stores a corresponding value of sum against it and I use that in the base cases. But dry running it, it doesn't look right.</p>
  
  <p>Any hints/help much appreciated. </p>
  
  <pre><code>void minCoins_Helper2(std::vector&lt;int&gt; coins, int sum, int index, int currCoins, int &amp;min){
      // Base cases
      if(index == coins.size())
          return;
      if(sum &lt; 0)
          return;
      if(sum == 0){
          if(currCoins &lt; min)
              min = currCoins;
          return;
      }
      // Include the coin
      minCoins_Helper2(coins, sum - coins[index], index, currCoins+1, min);
      // Exclude the coin
      minCoins_Helper2(coins, sum, index+1, currCoins, min);
  }
  
  int minCoins2(std::vector&lt;int&gt; coins, int sum){
      int min = INT_MAX;
      minCoins_Helper2(coins, sum, 0, 0, min);;
      return min;
  }
  </code></pre>