Partition Equal Subset Sum
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

Question

Partition Equal Subset Sum

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

Accepted Answer

Let isSubsetSum(arr, n, sum/2) be the function that returns true if
there is a subset of arr[0..n-1] with sum equal to sum/2

The isSubsetSum problem can be divided into two subproblems
a) isSubsetSum() without considering last element
(reducing n to n-1)
b) isSubsetSum considering the last element
(reducing sum/2 by arr[n-1] and n to n-1)
If any of the above subproblems return true, then return true.
isSubsetSum (arr, n, sum/2) = isSubsetSum (arr, n-1, sum/2) ||
isSubsetSum (arr, n-1, sum/2 - arr[n-1])

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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

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

Time Complexity: O(2^n)Explanation:

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).

Accepted Answer

Using Memoization

Approach: The previous approach uses recursion which has many overlapping subproblems. i.e recursive function computes the same sub-problems again and again. So we can use memoization to overcome the overlapping subproblems.

To reiterate memoization is when we store the results in a lookup 'ARR'ay('DP') of all previously solved subproblems and use the results from the 'DP' if we encounter the problem that has already been solved.

Since there are two states that are changing in the recursive function 'CANPARTITIONUTIL'() i.e 'CURRENTINDEX', and 'SUBSETSUM' So we create a 2-dimensional array 'DP'[][] to store all the subproblems.

Steps:

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

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

If 'CURRENTINDEX' reaches the end of 'ARR' array or 'SUBSETSUM' < 0, return false.
If 'SUBSETSUM' is equal to 0, return true as we found the subset.
If we already solve the same subproblem for index 'CURRENTINDEX' and sum 'SUBSETSUM', return 'DP'['CURRENTINDEX']['SUBSETSUM'].
Otherwise, we have two choices either to include or exclude element at index 'CURRENTINDEX':
- 'CANPARTITIONUTIL'('ARR', 'CURRENTINDEX' + 1, 'SUBSETSUM' - 'ARR'['CURRENTINDEX'], 'DP').
- 'CANPARTITIONUTIL'('ARR', 'CURRENTINDEX' + 1, 'SUBSETSUM', 'DP')
Then store the results of both in 'DP'['CURRENTINDEX']['SUBSETSUM'], and return 'DP'['CURRENTINDEX']['SUBSETSUM'].

Space Complexity: OtherExplanation:

O(N * S), where ‘N’ is the size of the array, and ‘S’ is the sum of all elements in the given array.

In the worst case, extra space is required to create the 2-D dp array of size N*S i.e O(N * S), and also for the recursion stack. Hence the overall complexity will be O(N * S).

Time Complexity: OtherExplanation:

O(N * S), where ‘N’ is the size of the array, and ‘S’ is the sum of all elements in the given array.

In the worst case, we will find the sum of all elements in the given array takes O(N) time. The 2-D array dp stores the results for all the subproblems, we can conclude that we will not have more than N*S subproblems, therefore, it takes O(N * S) time. Hence the overall complexity will be O(N * S).

Accepted Answer

Dynamic Programming

Approach:

The idea is to use a bottom-up dynamic programming approach instead of a memoization approach. Let us assume 'DP'['I']['J'] means whether the specific 'SUM' j can come from the first I numbers in an array. If we can pick such a series of numbers from 0-i whose 'SUM' is j, 'DP'['I']['J'] is true, otherwise, it is false.
Essentially, we want to find if we can make all possible 'SUM's with every subset. This means 'DP'['I']['J'] will be ‘true’ if we can make 'SUM' j from the first I numbers.
For the base case, we set 'DP'[0][0] to true since with 0 elements a subset-'SUM' of 0 is possible.
Now, 'DP'['I']['J'] is true if 'DP'[i-1]['J'] is true As we skipped this element, and took the 'SUM' of the previous result or 'DP'['I'-1]['J' - element’s value] assuming this isn’t out of range(meaning that we added this value to our subset-'SUM' so we look at the 'SUM'-current element’s value).
If 'DP'['N']['SUM'/2] is true that means we were able to find a 'SUM' of 'SUM'/2 out of 'N' elements which is what we want to check.

Steps:

Find the 'SUM' of all elements of array say 'TOTALSUM'.
If 'TOTALSUM' is not divisible by 2 return false, as array cant be partitioned into two equal subsets.
Create a new auxiliary array 'DP' of length 'N' * 'TOTALSUM' / 2.
Iterate the given array, now for each index 'I' we run a loop from 0 to 'TOTALSUM' / 2 then at each index 'J' we have two choices:
- Exclude the number. In this case, we will see if we can get 'J' from the subset excluding this number: 'DP'[i-1]['J']
- Include the number if its value is not more than 'J'. In this case, we will see if we can find a subset to get the remaining 'SUM': 'DP'['I' - 1]['J' - 'NUMS'['I']]
If either of the two above choices is true then we can find a subset of numbers with 'SUM' 'J'.
At last, return 'DP'['N']['TOTALSUM' / 2].

Space Complexity: OtherExplanation:

O(N * S), where ‘N’ is the size of the array, and ‘S’ is the sum of all elements in the given array.

In the worst case, extra space is required to create the DP array of size N*S. Hence the overall complexity will be O(N * S).

Time Complexity: OtherExplanation:

O(N * S), where ‘N’ is the size of the array, and ‘S’ is the sum of all elements in the given array.

In the worst case, we will find the sum of all elements in the given array that takes O(N). Traversing the dp array of size N*S i.e O(N * S). Hence the overall complexity will be O(N * S).

Accepted Answer

Using 1-D array

Approach: We see in a previous approach that we only need current index 'I' , and previous index 'I' - 1, and the rest of the indexes are a waste of space, So, we can achieve the same using a one-dimensional array as well.

Steps:

Find the sum of all elements of the array says 'TOTALSUM'.
If 'TOTALSUM' is not divisible by 2 return false, as array cant be partitioned into two equal subsets.
Create a new auxiliary 1-D array 'DP' of length 'TOTALSUM'/2.
Iterate the given array, now for each index 'I' we run a loop from 'TOTALSUM'/2 to 0 then at each index 'J' we check:
- If 'J'- 'ARR'['I'-1]>=0 then 'DP'['J'] = 'DP'['J' - 'NUMS'['I' - 1]] or 'DP'['J']
At last, return 'DP'['TOTALSUM'/ 2].

Space Complexity: O(n)Explanation:

O(S), where ‘S’ is the sum of all elements in the given array.

In the worst case, extra space is required to create the DP array of size S. Hence the overall complexity will be O(S).

Time Complexity: OtherExplanation:

O(N * S), where ‘N’ is the size of the array, and ‘S’ is the sum of all elements in the given array.

In the worst case, we will find the sum of all elements in the given array that takes O(N). Traversing the given array O(N), and for each index, we run a loop O(S). Hence the overall complexity will be O(N * S).

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:

Input Format:

Output Format:

Note:

Constraints:

Top Ola Cabs SDE-2 interview questions & answers

Popular interview questions of SDE-2