Divide set into two subsets of equal sum and maximum this sum

Question

Original Question: https://stackoverflow.com/questions/47492444/create-two-sub-lists-from-given-list-of-integers-with-equal-sum-and-maximize-thi

You are given a list S of positive integers. You are to create two sub-lists S1 and S2 taking elements from S, such that

sum of S1 is equal to sum of S2 maximize this sum and output it no need to put all elements of S into S1 or S2, you can ignore any number of elements of S. For example: if S= [2, 6, 5, 1, 2, 5] then answer will be 10, (with S1= [6, 2, 2] and S2= [5, 5] with ignoring 1)

Constraints:

(i) if N is length of S, 1<= N <=50

(ii) if MAX is the maximum element of S, 1<= MAX <=1000

(iii) if SUM is the total sum of S, 1<= SUM <=1000

I can think only below brute-force approach:

as 1<=SUM<=1000, our answer can be between 0 and 500.

so, for each subset (SUB) of S, I am finding sum (SUBSUM) of SUB and checking whether SUBSUM can be obtained from list S - SUB using subset-sum algorithm. I am returning largest such SUBSUM. So my time complexity is O(N*(SUM/2)*2^N)

Any faster way?

Any DP approach?

Answer 1

This is Partition problem. And is NP-Complete. There cannot be a deterministic P-time algorithm to solve this efficiently for sufficiently large $n$ unless $P=NP$.

Answer 2

I am pretty sure you have found an answer by now, but I am leaving an answer here for any possible future reference.

The previous answer said that this problem is NP-Complete under sufficiently large n, but I maintain that this problem can be solved in O(n*sum) time, via a DP-approach.

Here's how (in C++, and I'm sorry that my code is a little messy):

#include<cstdio>
int previous_index[51][1001], val[51], n;
bool chk[51];
int abs(int a){ return a>0?a:-a; }
void fill_table_with_minus_one(int n,int sum){
    for(int i=1;i<=n;i++)
        for(int s=0;s<=sum;s++)
            previous_index[i][s] = -1;
}
void fill_table(int ind, int sum_till_ind_minus_one, int last_summed){
    if(ind > n) return;
    if(previous_index[ind][sum_till_ind_minus_one] != -1) return;
    fill_table(ind+1, sum_till_ind_minus_one, last_summed);
    previous_index[ind][sum_till_ind_minus_one + val[ind]] = last_summed;
    fill_table(ind+1, sum_till_ind_minus_one + val[ind], ind);
}
int main(){
    int sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&val[i]);
        sum += val[i];
    }
    fill_table_with_minus_one(n,sum);
    fill_table(1,0,0);
    int saveind=0,saveval=0;
    for(int local_sum = 0;local_sum <= sum/2; local_sum++)
        for(int i=1;i<=n;i++)
            if(previous_index[i][local_sum] != -1){
                saveind = i;
                saveval = local_sum;
            }
    while(saveind > 0){
        printf("%d %d\n",saveind, saveval);
        chk[saveind] = 1;
        int temp = val[saveind];
        saveind = previous_index[saveind][saveval];
        saveval -= temp;
    }
    for(int i=1;i<=n;i++)
        if(chk[i]) 
            printf("%d ",val[i]);
    printf("\n");
    for(int i=1;i<=n;i++)
        if(!chk[i])
            printf("%d ",val[i]);
}

First we scanned the input, saved to n and val[], then filled the DP table according to the following rules:

1. previous_index[i][sum] shall have a value of -1 if and only if the value sum cannot be reached with by adding/not adding one of each first i numbers;

2. If val[i] was added to the available values until the i-1 th, then the previous_index[i][sum] shall store the index of the number that was previously added, that is, before val[i]. If none was, then 0 will be stored.

And then now we have the values, it isn't really that hard to track back and print the values.