Partition Equal Subset Sum

Moderate
0/80
Average time to solve is 25m
183 upvotes
Asked in companies
OlaOracleSAP Labs

Problem statement

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?
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
6
3 1 1 2 2 1
5
5 6 5 11 6
Sample Output 1:
true
false
Explanation Of Sample Input 1:
For the first test case, the array can be partitioned as ([2,1,1,1] and [3, 2]) or ([2,2,1], and [1,1,3]) with sum 5.

For the second test case, the array can’t be partitioned.
Sample Input 2:
2
9
2 2 1 1 1 1 1 3 3
6
8 7 6 12 4 5
Sample Output 2:
false
true
Hint

Think of brute force and try to generate all the possible subsets of the array, and check if its sum is equal to totalSum/2, where totalSum represents the sum of all elements in an array.

Approaches (4)
Brute Force

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.
Time Complexity

O(2 ^ N), where ‘N’ is the size of the array.

 

In the worst case, we will find the sum of all elements in the given array takes O(N) time. For every index of the given array, we have two choices i.e either to include that element or exclude the element in subset-sum. Hence the overall complexity will be O(2 ^ N).

Space Complexity

O(N), where ‘N’ is the size of the array.

 

In the worst case, extra space is required for the recursion stack.

Code Solution
(100% EXP penalty)
Partition Equal Subset Sum
Full screen
Console