title: Finding 2 equal sum sub-sequences, with maximum sum?
body: <blockquote>
    <p>I have removed all the storylines for this question. </p>
    
    <p><code>Q.</code> You are given N numbers. You have to find 2 equal sum sub-sequences, with maximum sum. You don't necessarily need to use all numbers.</p>
  </blockquote>
  
  <p><strong>Eg 1:-</strong></p>
  
  <pre><code>5
  1 2 3 4 1
  
  Sub-sequence 1 : 2 3 // sum = 5
  Sub-sequence 2 : 4 1 // sum = 5
  
  Possible Sub-sequences with equal sum are 
  {1,2} {3}   // sum = 3
  {1,3} {4}   // sum = 4
  {2,3} {4,1} // sum = 5
  
  Out of which 5 is the maximum sum.
  </code></pre>
  
  <p><strong>Eg 2:-</strong></p>
  
  <pre><code>6
  1 2 4 5 9 1
  
  Sub-sequence 1 : 2 4 5   // sum = 11
  Sub-sequence 2 : 1 9 1   // sum = 11
  The maximum sum you can get is 11
  </code></pre>
  
  <p><strong>Constraints:</strong></p>
  
  <pre><code>5 &lt;= N &lt;= 50
  
  1&lt;= number &lt;=1000
  
  sum of all numbers is &lt;= 1000
  
  Important: Only &lt;iostream&gt; can be used. No STLs.
  
  N numbers are unsorted.
  
  If array is not possible to split, print 0.
  
  Number of function stacks is limited. ie your recursive/memoization solution won't work.
  </code></pre>
  
  <p><strong>Approach 1:</strong></p>
  
  <p>I tried a recursive approach something like the below:</p>
  
  <pre><code>#include &lt;iostream&gt;
  using namespace std;
  
  bool visited[51][1001][1001];
  int arr[51];
  int max_height=0;
  int max_height_idx=0;
  int N;
  
  void recurse( int idx, int sum_left, int sum_right){
      if(sum_left == sum_right){
          if(sum_left &gt; max_height){
              max_height = sum_left;
              max_height_idx = idx;
          }
      }
  
  
      if(idx&gt;N-1)return ;
  
      if(visited[idx][sum_left][sum_right]) return ;
  
      recurse( idx+1, sum_left+arr[idx], sum_right);
      recurse( idx+1, sum_left         , sum_right+arr[idx]);
      recurse( idx+1, sum_left         , sum_right);
  
      visited[idx][sum_left][sum_right]=true;
  
      /*
         We could reduce the function calls, by check the visited condition before calling the function.
         This could reduce stack allocations for function calls. For simplicity I have not checking those conditions before function calls.
         Anyways, this recursive solution would get time out. No matter how you optimize it.
         Btw, there are T testcases. For simplicity, removed that constraint.
      */
  }
  
  int main(){
      ios_base::sync_with_stdio(false);
      cin.tie(nullptr);
  
      cin&gt;&gt;N;
      for(int i=0; i&lt;N; i++)
          cin&gt;&gt;arr[i];
  
      recurse(0,0,0);
  
      cout&lt;&lt; max_height &lt;&lt;"\n";
  }
  </code></pre>
  
  <p><code>NOTE:</code> Passes test-cases. But time out.</p>
  
  <p><strong>Approach 2:</strong></p>
  
  <pre><code>I also tried, taking advantage of constraints.
  
  Every number has 3 possible choice:
      1. Be in sub-sequence 1
      2. Be in sub-sequence 2
      3. Be in neither of these sub-sequences 
  
  So
      1. Be in sub-sequence 1 -&gt; sum +  1*number
      2. Be in sub-sequence 2 -&gt; sum + -1*number
      3. None             -&gt; sum
  
  Maximum sum is in range -1000 to 1000. 
  So dp[51][2002] could be used to save the maximum positive sum achieved so far (ie till idx).
  </code></pre>
  
  <p><strong>CODE:</strong></p>
  
  <pre><code>#include &lt;iostream&gt;
  using namespace std;
  
  int arr[51];
  int N;
  int dp[51][2002];
  
  int max3(int a, int b, int c){
      return max(a,max(b,c));
  }
  int max4(int a, int b, int c, int d){
      return max(max(a,b),max(c,d));
  }
  
  int recurse( int idx, int sum){
  
      if(sum==0){
          // should i perform anything here?
      }
  
      if(idx&gt;N-1){
          return 0;
      }
  
      if( dp[idx][sum+1000] ){
          return dp[idx][sum+1000];
      }
  
      return dp[idx][sum+1000] = max3 (
                                  arr[idx] + recurse( idx+1, sum + arr[idx]),
                                      0    + recurse( idx+1, sum - arr[idx]),
                                      0    + recurse( idx+1, sum           )
                                 )  ;
  
      /*
          This gives me a wrong output.
  
          4
          1 3 5 4
      */
  }
  
  
  int main(){
      ios_base::sync_with_stdio(false);
      cin.tie(nullptr);
  
      cin&gt;&gt;N;
      for(int i=0; i&lt;N; i++)
          cin&gt;&gt;arr[i];
  
      cout&lt;&lt; recurse(0,0) &lt;&lt;"\n";
  
  }
  </code></pre>
  
  <p>The above code gives me wrong answer. Kindly help me with solving/correcting this memoization.</p>
  
  <p>Also open to iterative approach for the same.</p>