Count of Subsets that can be partitioned into two non empty sets with equal Sum

Given an array Arr[] of size N, the task is to find the count of subsets of Arr[] that can be partitioned into two non-empty groups having equal sum.

Examples: 

Input: Arr[] = {2, 3, 4, 5}
Output: 2
Explanation: The subsets are: 
{2, 3, 5} which can be split into {2, 3} and {5}
{2, 3, 4, 5} which can be split into {2, 5} and {3, 4}

Input: Arr[] = {1, 2, 3, 4, 5}
Output: 7

Naive Approach: The simplest approach is to generate all subsets and for each subset S, if it has a sum of A, find all the subsets of S and check if it has a sum of A/2. 

Time Complexity: O(4^N) 
Auxiliary Space: O(1)

Efficient Approach: The idea to solve the problem efficiently is to use the meet in the middle technique. 

• Split the array equally into two halves and for each half compute all the possible subsets.
• For elements included in a subset in either half, assign it to either first group or second group by adding to or subtracting from the variable ‘sum‘ ( sum is initialized to 0).
• For the first half of the array, if an element is assigned to the first group simply add its value to sum, else subtract it. For the second half of the array, if an element is assigned to the first group subtract it from sum, else add it.

Follow the below steps to solve the problem:

• Declare a global Boolean array ‘canSplit’ of size(1 << N) to store the result of each subset if it can be partitioned into two groups having equal sum.
• Declare a global Map to assign the sum of a subset to an ID, and to find if there is already a subset with the same sum as current subset.
• Declare a global Vector of Vector to store all the bitmasks having the same sum together.
• Define a Recursive function say makeSubsets1(i, sum, mask) to construct all subsets from the first half of the array.
  • Base Case, If i == N/2, then the first half of the array has been traversed completely.
    • If the sum of the current subset represented by bitmask is different from the already formed subsets, then increment the variable ID by 1 and assign the value of sum to this ID.
    • Retrieve the ID number of the current sum.
    • Add the subset represented by the bitmask to the vector of the retrieved ID.
  • The number at the current index can be:
    • Excluded from the current subset.
    • Included to the first group of the subset. In this case, we add the number to ‘sum‘.
    • Included to the second group of the subset. In this case, we subtract the number from ‘sum‘.
• Define a Recursive function say makeSubsets2(i, sum, mask) to construct all subsets from the second half of the array.
  • Base Case, If i == N, then the entire array has been traversed completely starting from the middle.
    • If any subset in the first half of the array has the same sum as that of the current subset, then the Bitwise OR of the two forms a valid subset as they have the same unbalance value. In other words if :
      • ∑(First group)₁ – ∑(Second group)₁  = ∑(Second group)₂ – ∑(First group)₂, by rearraning terms,
      • ∑(First group)₁ + ∑(First group)₂ = ∑(Second group)₁ + ∑(Second group)₂
    • Hence the Bitwise OR of the two subsets can be divided into two groups having equal sums. Iterate through all the subsets of first half having the same sum and mark the Bitwise OR of it with the current subset from the second half as ‘true‘ indicating a valid subset.
  • The number at the current index can be:
    • Excluded from the current subset.
    • Included to the second group of the subset. In this case, we add the number to ‘sum‘.
    • Included to the first group of the subset. In this case, we subtract the number from ‘sum‘.
• Iterate through all the subsets and increase the answer by 1 if canSplit[mask] = true .
• Print the answer.

Below is the code for the above approach:

2

Time Complexity: O(6^N/2). 

• Generating all subsets from the first and second half of the array takes O(3^N/2).
• In the worst case all the subsets of first half may be matched with the current subset of second half taking O(2^N/2).
• Hence overall time complexity is O(3^N/2 * 2^N/2) = O(6^N/2).

Auxiliary Space: O(2^N)