Finding 2 equal sum sub-sequences, with maximum sum?

Question

I have removed all the storylines for this question.

Q. 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.

Eg 1:-

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.

Eg 2:-

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

Constraints:

5 <= N <= 50

1<= number <=1000

sum of all numbers is <= 1000

Important: Only <iostream> 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.

Approach 1:

I tried a recursive approach something like the below:

#include <iostream>
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 > max_height){
            max_height = sum_left;
            max_height_idx = idx;
        }
    }


    if(idx>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>>N;
    for(int i=0; i<N; i++)
        cin>>arr[i];

    recurse(0,0,0);

    cout<< max_height <<"\n";
}

NOTE: Passes test-cases. But time out.

Approach 2:

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 -> sum +  1*number
    2. Be in sub-sequence 2 -> sum + -1*number
    3. None             -> 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:

#include <iostream>
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>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>>N;
    for(int i=0; i<N; i++)
        cin>>arr[i];

    cout<< recurse(0,0) <<"\n";

}

The above code gives me wrong answer. Kindly help me with solving/correcting this memoization.

Also open to iterative approach for the same.

Answer 1

Idea of your second approach is correct, it's basically a reduction to the knapsack problem. However, it looks like your code lacks clear contract: what the recurse function is supposed to do.

Here is my suggestion: int recurse(int idx, int sum) distributes elements on positions idx..n-1 into three multisets A, B, C such that sum+sum(A)-sum(B)=0 and returns maximal possible sum(A), -inf otherwise (here -inf is some hardcoded constant which serves as a "marker" of no answer; there are some restrictions on it, I suggest -inf == -1000).

Now you're to write a recursive backtracking using that contract and then add memoization. Voila—you've got a dynamic programming solution.

In recursive backtracking we have two distinct situations:

1. There are no more elements to distribute, no choices to make: idx == n. In that case, we should check that our condition holds (sum + sum(A) - sum(B) == 0, i.e. sum == 0) and return the answer. If sum == 0, then the answer is 0. However, if sum != 0, then there is no answer and we should return something which will never be chosen as the answer, unless there are no answer for the whole problem. As we modify returning value of recurse and do not want extra ifs, it cannot be simply zero or even -1; it should be a number which, when modified, still remains "the worst answer ever". The biggest modification we can make is to add all numbers to the resulting value, hence we should choose something less or equal to negative maximal sum of numbers (i.e. -1000), as existing answers are always strictly positive, and that fictive answer will always be non-positive.
2. There is at least one remaining element which should be distributed to either A, B or C. Make the choice and choose the best answer among three options. Answers are calculated recursively.

Here is my implementation:

const int MAXN = 50;
const int MAXSUM = 1000;

bool visited[MAXN + 1][2 * MAXSUM + 1]; // should be filled with false
int dp[MAXN + 1][2 * MAXSUM + 1]; // initial values do not matter

int recurse(int idx, int sum){
    // Memoization.
    if (visited[idx][sum + MAXSUM]) {
        return dp[idx][sum + MAXSUM];
    }
    // Mark the current state as visited in the beginning,
    // it's ok to do before actually computing it as we're
    // not expect to visit it while computing.
    visited[idx][sum + MAXSUM] = true;

    int &answer = dp[idx][sum + MAXSUM];

    // Backtracking search follows.
    answer = -MAXSUM;  // "Answer does not exist" marker.

    if (idx == N) {
        // No more choices to make.
        if (sum == 0) {
            answer = 0;  // Answer exists.
        } else {
            // Do nothing, there is no answer.
        }
    } else {
        // Option 1. Current elemnt goes to A.
        answer = max(answer, arr[idx] + recurse(idx + 1, sum + arr[idx]));
        // Option 2. Current element goes to B.
        answer = max(answer, recurse(idx + 1, sum - arr[idx]));
        // Option 3. Current element goes to C.
        answer = max(answer, recurse(idx + 1, sum));
    }
    return answer;
}

Answer 2

Here is a simple dynamic programming based solution for anyone interested, based on the idea suggested by Codeforces user lemelisk here. Complete post here. I haven't tested this code completely though.

#include <iostream>
using namespace std;

#define MAXN 20 // maximum length of array
#define MAXSUM 500 // maximum sum of all elements in array
#define DIFFSIZE (2*MAXSUM + 9) // possible size of differences array (-maxsum, maxsum) + some extra

int dp[MAXN][DIFFSIZE] = { 0 };
int visited[DIFFSIZE] = { 0 }; // visited[diff] == 1 if the difference 'diff' can be reached 
int offset = MAXSUM + 1; // offset so that indices in dp table don't become negative
// 'diff' replaced by 'offset + diff' below everywhere

int max(int a, int b) {
    return (a > b) ? a : b;
}
int max_3(int a, int b, int c) {
    return max(a, max(b, c));
}

int main() {
    int a[] = { 1, 2, 3, 4, 6, 7, 5};
    int n = sizeof(a) / sizeof(a[0]);
    int *arr = new int[n + 1];
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        arr[i] = a[i - 1]; // 'arr' same as 'a' but with 1-indexing for simplicity
        sum += arr[i];
    } // 'sum' holds sum of all elements of array

    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < DIFFSIZE; j++)
            dp[i][j] = INT_MIN;
    }

    /*
    dp[i][j] signifies the maximum value X that can be reached till index 'i' in array such that diff between the two sets is 'j'
    In other words, the highest sum subsets reached till index 'i' have the sums {X , X + diff}
    See http://codeforces.com/blog/entry/54259 for details
    */

    // 1 ... i : (X, X + diff) can be reached by 1 ... i-1 : (X - a[i], X + diff)
    dp[0][offset] = 0; // subset sum is 0 for null set, difference = 0 between subsets
    visited[offset] = 1; // initially zero diff reached

    for (int i = 1; i <= n; i++) {
        for (int diff = (-1)*sum; diff <= sum; diff++) {
            if (visited[offset + diff + arr[i]] || visited[offset + diff - arr[i]] || visited[offset + diff]) { 
                // if difference 'diff' is reachable, then only update, else no need
                dp[i][offset + diff] = max_3 
                (
                    dp[i - 1][offset + diff], 
                    dp[i - 1][offset + diff + arr[i]] + arr[i], 
                    dp[i - 1][offset + diff - arr[i]] 
                );
                visited[offset + diff] = 1;
            }
        }
        /*
        dp[i][diff] = max {
        dp[i - 1][diff] : not taking a[i] in either subset
        dp[i - 1][diff + arr[i]] + arr[i] : putting arr[i] in first set, thus reducing difference to 'diff', increasing X to X + arr[i]
        dp[i - 1][diff - arr[i]] : putting arr[i] in second set
        initialization: dp[0][0] = 0
        */

        // O(N*SUM) algorithm
    }
    cout << dp[n][offset] << "\n";
    return 0;
}

Output:

14