Partition Equal Subset Sum

Posted: 17 Nov, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given an array 'ARR' of 'N' positive integers. Your task is to find if we can partition the given array into two subsets such that the sum of elements in both subsets is equal.

For example, let’s say the given array is [2, 3, 3, 3, 4, 5], then the array can be partitioned as [2, 3, 5], and [3, 3, 4] with equal sum 10.

Follow Up:

Can you solve this using not more than O(S) extra space, where S is the sum of all elements of the given array?
Input Format:
The first line of input contains an integer 'T' representing the number of test cases or queries to be processed.
Then the test case follows.

The first line of each test case contains an integer 'N', denoting the size of the array.

The second line of each test case contains 'N' single space-separated integers representing the array elements.
Output Format:
For each test case, print “true” or “false” denoting whether we can partition into two equal subset-sum or not, in a separate line. 
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= 'T' <= 10
1 <= 'N' <= 100 
1 <= 'ARR'[i] <= 100

Time Limit: 1 sec
Approach 1

Approach: The key point to notice here is that we have to partition an array into two equal subsets sum so two equal subsets must have the sum equal to 'TOTALSUM'/2, where 'TOTALSUM' represents the sum of all elements in the given array, and also 'TOTALSUM' should be even as we cant partitioned an array into two equal if 'TOTALSUM' is odd,  So now the problem is to check if there is any subset in a given array with sum 'TOTALSUM'/2. And now this problem is similar to the classical 0/1 Knapsack Problem in which in the recursion call at any index, we have two choices whether to include that element in sum or exclude that element. Now if we choose the current number to add to the sum then recur for index 'I'+1  or If we don’t choose the current index element to sum then recur for index 'I'+1 and this way we check if there is a subset with sum 'TOTALSUM'/2 in the given array. 

 

Steps:

  • Find the sum of all elements of the array that says 'TOTALSUM'.
  • If 'TOTALSUM' is not divisible by 2 return false, as array cant be partitioned into two equal subsets.
  • Define and call a helper function, 'CANPARTITIONUTIL'('ARR', 'CURRENTINDEX', 'SUBSETSUM') to check if there is subset with sum to 'TOTALSUM'/2, where 'ARR' is the given array and 'CURRENTINDEX' denotes the current index of given array and return 'CANPARTITIONUTIL'('ARR', 0, 'TOTALSUM' / 2)

 

Boolean 'CANPARTITIONUTIL'('ARR', 'CURRENTINDEX','SUBSETSUM')

  • If 'CURRENTINDEX' reaches the end of the 'ARR' array or 'SUBSETSUM' < 0, return false.
  • If 'SUBSETSUM' is equal to 0, return true, as we found a subset.
  • Then we have two choices either to include or exclude element at index 'CURRENTINDEX' in 'SUBSETSUM':
    • 'CANPARTITIONUTIL'('ARR', 'CURRENTINDEX' + 1, 'SUBSETSUM' - 'ARR'['CURRENTINDEX'])
    • 'CANPARTITIONUTIL'('ARR', 'CURRENTINDEX' + 1, 'SUBSETSUM')
  • If anyone of above choices return true, then return true.
  • Else return false.
Try Problem