title: Reduce subsequence problem complexity from exponential to polynomial?
body: <p>I am working on <a href="https://practice.geeksforgeeks.org/problems/subset-with-sum-divisible-by-m/0" rel="nofollow noreferrer">the following problem</a>:</p>
  
  <blockquote>
    <p>Given a set of non-negative distinct integers, and a value m, determine if there is a subset of the given set with sum divisible by m.</p>
    
    <p><strong>Input:</strong> The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains an integer N and M where N denotes the size of the array and M is the number for which we have to check the divisibility.  The second line of each test case contains N space separated integers denoting elements of the array A[ ].</p>
    
    <p><strong>Output:</strong> If there is a subset which is divisible by M print '1' else print '0'.</p>
  </blockquote>
  
  <p>I have tried a recursive solution:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include&lt;unordered_map&gt;
  using namespace std;
  
  bool find_it(int a[],int &amp;m,int n,int sum) {
      if ((sum%m)==0 &amp;&amp; sum&gt;0)
          return true;
      if (n==0)
          return false;
      return find_it(a,m,n-1,sum) || find_it(a,m,n-1,sum-a[n-1]);
  }
  
  int main() {
      int tc;
      cin &gt;&gt; tc;
      while (tc--) {
          int n,m;
          cin &gt;&gt; n &gt;&gt; m;
          int a[n];
          int sum = 0;
          for (int i=0;i&lt;n;i++) {
              cin &gt;&gt; a[i];
              sum += a[i];
          }
          bool answer = find_it(a,m,n,sum);
          cout &lt;&lt; answer &lt;&lt; "\n";
      }
     return 0;
  }
  </code></pre>
  
  <p>Which works fine and get accepted, but then I tried top-down approach, and am getting TLE ("Time Limit Exceeded").  What am I doing wrong in this memoization?</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include&lt;unordered_map&gt;
  using namespace std;
  
  bool find_it(
      int a[], int &amp;m, int n, int sum,
      unordered_map&lt;int,unordered_map&lt;int,bool&gt;&gt; &amp;value,
      unordered_map&lt;int,unordered_map&lt;int,bool&gt;&gt; &amp;visited){
  
      if ((sum%m)==0 &amp;&amp; sum&gt;0)
          return true;
      if(n==0)
          return false;
  
      if(visited[n][sum]==true)
          return value[n][sum];
  
      bool first = false,second = false;
      first = find_it(a,m,n-1,su1m,value,visited);
  
      if(sum&lt;a[n-1])
      {
          second=false;
      }
      else
      second = find_it(a,m,n-1,sum-a[n-1],value,visited);
  
      visited[n][sum] = true;
      value[n][sum] = first || second;
      return value[n][sum];
  }
  
  int main() {
      int tc;
      cin &gt;&gt; tc;
      while (tc--) {
          int n,m;
          cin &gt;&gt; n &gt;&gt; m;
          int a[n];
          int sum = 0;
          for (int i=0;i&lt;n;i++) {
              cin &gt;&gt; a[i];
              sum+=a[i];
          }
          unordered_map&lt;int,unordered_map&lt;int,bool&gt;&gt; value;
          unordered_map&lt;int,unordered_map&lt;int,bool&gt;&gt; visited;
          cout &lt;&lt; find_it(a,m,n,sum,value,visited) &lt;&lt; "\n";
      }
      return 0;
  }
  </code></pre>