Equal Sum Subset Partition Problem

Given an array s of n integers, partition it into two non-empty subsets, s1 and s2, such that the sum of all elements in s1 is equal to the sum of all elements in s2. Return a boolean array of size n where i-th element is True if i-th element of s belongs to s1 and False if it belongs to s2. Any valid answer will be accepted. If such partitioning is not possible, return an empty array.

Example

Input: n = 6, s = [10, -3, 7, 2, 1, 3]

Output: [True, True, False, False, False, True]

There are multiple partitionings where s1 sums up to 10 and s2 sums up to 10; they are all correct answers:

1) s1 = [ 10 , -3 , 3 ] and s2 = [ 7 , 2 , 1 ] (Sample output)

2) s1 = [ 7 , 2 , 1 ] and s2 = [ 10 , -3 , 3 ]

3) s1 = [10] and s2 = [-3, 3, 7, 2, 1]

4) s1 = [-3, 3, 7, 2, 1] and s2 = [10]

5) s1 = [10, -3, 2, 1] and s2 = [7, 3]

6) s1 = [7, 3] and s2 = [10, -3, 2, 1]

Notes

Input Parameters: The first and only parameter of the function that is to be implemented is the array of integers s, that is to be partitioned. 

Output Format: If it is possible to partition the given array s in an above-said manner then return a boolean array of size n, where its i (0

Constraints:

● 1

● -100

Solution

We provided two solutions.

1) brute_force_solution

This partitioning problem can be reduced to finding a subset that sums up to half of the total sum. Also, if the value of the sum is odd then we cannot partition it into two equal subsets. So, in case the value of the sum is odd we simply return an empty array. 

In this approach, we iterate over all possible combinations of subsets of the given array and check if the current subset sums to sum/2. If we find one such subset, we declare this subset s1 (the remaining elements belong to s2 then).

Time Complexity:

O(n*2^n) where n is the number of elements in the given input array.

As we are iterating on all possible subsets i.e. 2^n subsets for an array of size n. Hence, we are doing O(2^n) iterations and then for each subset, we are computing its sum. To do this we need to iterate over each element of the subset that takes O(n) time of each individual subset. Hence, the total time complexity becomes O(2^n) * O(n) ~ O(n*2^n).

Auxiliary Space Used:

O(n) where n is the number of elements in the given input array. To generate all partitionings we recursively backtrack on all indexes of the array. Call stack might take up to O(n) space.

Apart from this we are only traversing on the given subarray multiple times for different subsets without maintaining any state information, hence we do not allocate any space for processing. The only space we allocate is the final return array that is of size n and hence the total auxiliary space complexity is O(n) + O(n) = O(n).

Space Complexity:

O(n) where n is the number of elements in the given input array.

Auxiliary space + the Input Space i.e. O(n) + O(n) = O(n).

// -------- START --------

// returns true if the result array subsets gives
// a valid partition for the array v
bool validator(vector &v, vector &subsets)
{
    // stores sum of subset s1
    int sum1 = 0;
    // stores sum of subset s2
    int sum2 = 0;
    // counts number of elements in s2
    int sz = count(subsets.begin(), subsets.end(), true);
    int n = v.size();
    // basic sanity check
    if (sz == 0 or sz == n or subsets.size() != n)
    {
        return false;
    }
    // loop into array v and calculate s1 and s2 sum
    for (int i = 0; i < n; i++)
    {
        // if 0 belongs to s1
        if (subsets[i] == 0)
            sum1 += v[i];
        // if 1 belongs to s1
        else if (subsets[i] == 1)
            sum2 += v[i];
        else
        { // invalid output
            return false;
        }
    }
    // check if subset sum s1 equals subset sum s2
    if (sum1 != sum2)
    {
        return false;
    }
    return true;
}

// resursive backtracking to generate all subset partition
void solver(vector &vis, vector &s, int idx, bool &solutionFound)
{
    if (idx == s.size())
    {
        // check if current partition is valid or not
        solutionFound = validator(s, vis);
        return;
    }

    if (!solutionFound)
    {
        solver(vis, s, idx + 1, solutionFound);
    }

    if (!solutionFound)
    {
        // add current idx element in subset 1
        vis[idx] = 1;
        solver(vis, s, idx + 1, solutionFound);
        // remove current element forom subset 1
        vis[idx] = solutionFound;
    }
}

vector equalSubSetSumPartition(vector &s)
{
    // flag to indicate if solution is found in
    // recursion
    bool solutionFound = false;
    vector resultSubset(s.size(), 0);
    // recursively generates all possible partitions
    // and checks for solution
    solver(resultSubset, s, 0, solutionFound);
    if (!solutionFound)
    {
        // empty the array if no result found
        resultSubset.clear();
    }
    // return the resultant subset partition
    return resultSubset;
}
// -------- END --------
	

2) optimal_solution:

As discussed in the brute force approach we have simply reduced this problem to a subset sum problem such that given an array s and we need to first check if a subset exists with the subset sum of sum/2. If it exists then we need to separate that subset from the rest of elements of the array. We will be using dynamic programming to solve this problem. Our first aim will be to check if a subset with sum sum/2 exists or not. To do so, we will be maintaining a 2D DP state as following : 

Boolean state(idx, sum).

Here, state(idx, sum) tells us if it is possible to get a subset sum of the sum provided the elements from 0 to idx of the given array.

Now, our state transition will look like below:

state(idx, sum) = state(idx - 1, sum) | state(idx - 1, sum - s[idx])

So, using the above state transition we will populate all our DP states. Now, we simply check the value of state(n-1, sum/2) (assumed 0-based array index). If it is true then it is possible to partition the given array and if it is false then once again we return an empty array.

Now, to get the partitioning we start a top-down lookup on our DP states. We start from the state(n-1, sum/2). If this state is true and state(n-2, sum/2) is false this means s[n-1] contributed to the subset sum and if it is false we go to state(n-2, sum/2) to identify our contributors of the subset sum of sum/2. We repeat this reverse DP transition until the point we reach the first index of the array or till the point, the required sum becomes 0. While doing these reverse DP transitions we also mark the contributed elements as s1 subset elements and rest of the array as s2 elements. Because the elements in our array can also be negative and hence we use a hash-based container like unordered_map in C++ to overcome this problem of negative indexing. Kindly, refer to the solution for implementation details.

Time Complexity:

O(n*range_sum) since this is a pseudo-polynomial time problem where n is the number of elements in the given input array and range_sum is the absolute difference between the maximum sum and the minimum sum possible in the given input array s.

As we are visiting all the DP states i.e. n*range_sum, hence we will be doing n*range_sum iterations and for each state, we are doing O(1) amount of work and also because of memorization each state is being visited once. Hence, the total time complexity of this solution is O(n*range_sum). 

Auxiliary Space Used:

O(n*range_sum) where n is the number of elements in the given input array and range_sum is the absolute difference between the maximum sum and the minimum sum possible in the given input array s.

Since we are using an auxiliary container of size n*range_sum to store the DP states. So, the auxiliary space complexity is O(n*range_sum).

Space Complexity:

O(n*range_sum) where n is the number of elements in the given input array and range_sum is the absolute difference between the maximum sum and the minimum sum possible in the given input array s.

Auxiliary space + the Input space i.e. O(n*range_sum) + O(n) → O(n*range_sum).

// -------- START --------

vector equalSubSetSumPartition(vector &s)
{
    // store min and max sum possible for given array
    int sum_neg = 0, sum_pos = 0;
    // calculate min and max subset sums
    for (auto val : s)
    {
        if (val < 0)
            sum_neg += val;
        else
            sum_pos += val;
    }

    // total sum of the array
    int sum = sum_pos + sum_neg;
    // Partition not possible
    if (sum & 1)
    {
        vector ret;
        // return empty array
        return ret;
    }

    int n = s.size();

    // dp state
    unordered_map dp[n];

    // base state
    // for idx 0 only one sum s[0] is possible
    dp[0][s[0]] = true;

    // iterate on all idx
    for (int i = 1; i < n; i++)
    {
        // iterate on all possible subset sum
        for (int val = sum_neg; val <= sum_pos; val++)
        {
            // dp state-transition

            // 1) state(i,val) = state(i-1,val) without taking current element
            dp[i][val] = dp[i - 1][val];

            // 2) if val == s[i], just taking ith element is sufficient
            if (val == s[i])
                dp[i][val] = true;
            else if (val - s[i] >= sum_neg)
            {
                // 3) state(i,val) = state(i-1,val-s[i]) when taking current element
                dp[i][val] |= dp[i - 1][val - s[i]];
            }
        }
    }

    int required = sum / 2;
    int idx = n - 1;

    // parition not possible
    if (!dp[idx][required])
    {
        vector ret;
        return ret;
    }

    // tracks partition elements
    vector resultSubset(s.size(), 0);
    // tracks count of elements included in S1
    int cnt = 0;
    while (idx >= 0)
    {
        if (idx != 0)
        {
            // reverse dp transition
            if (dp[idx][required] and !dp[idx - 1][required])
            {
                resultSubset[idx] = 1;
                cnt++;
                required -= s[idx];
                if (required == 0)
                    break;
            }
        }
        else
        {
            resultSubset[idx] = 1;
            cnt++;
        }
        idx--;
    }

    // if all elements are included in S1
    // All elements will be in S1 if total_sum = 0
    // case when s = [-2,2]
    // partition is not possible in this case
    if (cnt == n)
    {
        resultSubset.clear();
    }
    return resultSubset;
}

// -------- END --------