title: How to find size of largest subset of a sub-sequence equal to a sum
body: <p>I have <a href="https://www.hackerearth.com/challenge/college/hbc-2018-semi-finals/algorithm/d03a689c4cec4ec393a6e5df79e8b322/" rel="nofollow noreferrer">this</a> problem from hackerearth</p>
  
  <blockquote>
    <p>Given an array of N integers, C cards and S sum. Each card can be used
    either to increment or decrement an integer in the given array by 1.
    Find if there is any subset (after/before using any no.of cards) with
    sum S in the given array.</p>
    
    <p><strong>Input Format</strong></p>
    
    <p>First line of input contains an integer T which denotes the no. of
    testcases. Each test case has 2 lines of input. First line of each
    test case has three integers N(size of the array), S(subset sum) and
    C(no. of cards). Second line of each test case has N integers of the
    array(a1 to aN) seperated by a space.</p>
    
    <p><strong>Constraints</strong></p>
    
    <p>1&lt;=T&lt;=100 <br> 1&lt;=N&lt;=100 <br> 1&lt;=S&lt;=10000 <br> 0&lt;=C&lt;=100 <br> 1&lt;=ai&lt;=100</p>
    
    <p><strong>Output Format</strong></p>
    
    <p>Print TRUE if there exists a subset with given sum else print FALSE.</p>
  </blockquote>
  
  <p>So this is basically a variation of the subset sum problem, but instead of finding out whether a given subset with a sum <code>S</code> exists, we need to find the largest subset from sequence <code>index</code> to <code>N-1</code> that has a value of <code>s</code> and compare it's length with our <code>C</code> value to see if it is greater. If it is, then we have enough elements to modify the sum using our <code>C</code> cards, and then we print out our answer. Here is my code for that</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;algorithm&gt;
  #include &lt;vector&gt;
  using namespace std;
  
  int N, S, C;
  
  
  int checkSum(int index, int s, vector&lt;int&gt;&amp; a, vector&lt; vector&lt;int&gt; &gt;&amp; dP) {
  
      if (dP[index][s] != -1)
          return dP[index][s];
  
      int maxNums = 0;    // size of maximum subset array
  
      for (int i = index; i &lt; N; i++) {
  
          int newSum = s - a[i];
          int l = 0;
  
          if (newSum == 0) {
              l = 1;
          } if (newSum &gt; 0) {
  
              if (i &lt; (N-1)) {    // only if we can still fill up sum
                  l = checkSum(i + 1, newSum, a, dP);
  
                  if (l &gt; 0)      // if it is possible to create this sum
                      l++;        // include l in it
              } else {
                  // l stays at 0 for there is no subset that can create this sum
              }
  
          } else {
              // there is no way to create this sum, including this number, so skip it;
              if (i == (N-1))
                  break;      // don't go to the next level
  
              // and l stays at 0
          }
  
          if (l &gt; maxNums) {
              maxNums = l;
          }
      }
  
      dP[index][s] = maxNums;
      return maxNums;
  }
  
  
  int main() {
  
      int t;
      cin &gt;&gt; t;
  
      while (t--) {
          cin &gt;&gt; N &gt;&gt; S &gt;&gt; C;
          vector&lt;int&gt; a(N);
  
          for (int i = 0; i &lt; N; i++)
              cin &gt;&gt; a[i];
  
          vector&lt; vector&lt;int&gt; &gt; dP(N, vector&lt;int&gt;(S + C + 2, -1));
  
          bool possible = false;
  
          for (int i = 0; i &lt;= C; i++) {
              int l = checkSum(0, S-i, a, dP);
              int m = checkSum(0, S+i, a, dP);
  
              if ( (l &gt; 0 &amp;&amp; l &gt;= i) || (m &gt; 0 &amp;&amp; m &gt;= i) ) {
  
                  cout &lt;&lt; "TRUE" &lt;&lt; endl;
                  possible = true;
                  break;
              }
  
          }
  
          if (!possible)
              cout &lt;&lt; "FALSE" &lt;&lt; endl;
      }
  
      return 0;
  }
  </code></pre>
  
  <p>So basically, 0 means it's not possible to create a subset equal to s from elements index to N-1, and -1 means we haven't computed it yet. And any other value indicates the size of the largest subset that sums up to s. This code isn't passing all the test cases. What's wrong?</p>