Home » Interview coding problems/challenges

# Equal Sum partition

**Equal Sum partition**: Given a set of numbers, check whether it can be partitioned into two subsets or not such that the sum of elements in both subsets is same.

Submitted by Radib Kar, on March 13, 2020

**Description:**

This is a popular interview coding problem which has been featured in interview rounds of Amazon, Oyo rooms, Adobe.

**Problem statement:**

Given a set of numbers, check whether it can be partitioned into two subsets or not such that the sum of elements in both subsets is same.

**Input:**

First line contains * N*, the number of elements in the set and the second line contains the elements of the set.

**Output:**

Print **YES** if the given set can be partitioned into two subsets such that the sum of elements in both subsets is equal, else print **NO**.

**Example with explanation:**

N=5 Elements are: 3, 4, 6, 2, 5 Output: Yes The set can be partitioned into two subsets with equal sum, Which is, subset1: {3, 2, 5} with sum 10 subset2: {4, 6} with sum 10 Another example can be, N=6 Elements are; 1, 3, 4, 8, 5, 6 Output would be NO since there is no way to do so.

**Solution Approach:**

We would first check the recursive solution.

Let's create two subset initially where the first subset contains all the elements and the second one is an empty one.

We calculate the total sum and our function is:

bool EqualPartition(index,subset1Sum,subset2Sum)

So, initially the function call will be

bool EqualPartition(n-1,total_sum,0)

Where **n-1= index of last element**, which is **index**

**total_sum= total sum of all elements**, which is **subset1Sum**

**0= subset2Sum** initially

Now, our idea is to check by either including the indexed element in * subset2 *or by not including. And we will continue doing this recursively until we reach our base case.

Let's see the function definition:

Function EqualPartition(index,subset1Sum,subset2Sum): if subset1Sum==subset2Sum //our objective to find return true if index<0 return false return EqualPartition(index-1,subset1Sum-arr[index],subset2Sum+arr[index]) || EqualPartition(index-1,subset1Sum,subset2Sum) End Function

So the recursive definition consists of the case what we discussed above.

EqualPartition(index-1,subset1Sum-arr[index],subset2Sum+arr[index]) = add the current element(arr[index]) to subset2 EqualPartition(index-1,subset1Sum,subset2Sum) = ignore the current element and recur for other elements

So this recursive definition will generate a recursion tree where we can find many overlapping sub problems, hence we would solve by dynamic programing. The solution approach is similar to subset problem.

So we have to create the DP table and fill up the table as per the solution approach in this article.

So, we have * dp[n+1][sum+1]* filled up now.

* sum* = total sum of elements

How can we utilize this piece of information as our solution?

Not too tough. If * dp[i][sum/2]* is

*for*

**true***, it ensures that we have a subset which sums*

**i= 1 to n***. Thus the remaining subset will have to be also of sum*

**(sum/2)***.*

**(sum/2)**This means we can have two equal sum subset.

Now, the point is what if (* sum*) is

**odd**.

Check our second example.

**Elements are:** 1, 3, 4, 8, 5, 6**Sum=27** which is odd.**(sum/2)=13** with integer division.**dp[6][13] = true** as 8,5 sums to 13.

So we would get output **YES** but is it the solution?

What's the catch then?

The catch is if * sum* is

**odd**, the answer will be always

**NO**. You can't partition in two equal subsets.

So before doing anything, just check whether the total * sum* is

**odd**or not. If the

*is odd simply return*

**sum***else proceed with the further DP. This would optimize time too.*

**false****C++ Implementation:**

#include <bits/stdc++.h> using namespace std; bool equalsubset(vector<int> arr, int n) { int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; //cout<<sum<<endl; if (sum % 2 == 1) return false; bool dp[n + 1][sum + 1]; memset(dp, false, sizeof(dp)); for (int i = 0; i <= sum; i++) dp[0][i] = false; for (int i = 0; i <= n; i++) dp[i][0] = true; for (int i = 1; i <= sum; i++) { for (int j = 1; j <= n; j++) { if (i >= arr[j - 1]) dp[j][i] = dp[j - 1][i] | dp[j - 1][i - arr[j - 1]]; else dp[j][i] = dp[j - 1][i]; } } for (int i = 1; i <= n; i++) if (dp[i][sum / 2]) return true; return false; } int main() { int t, n, item; cout << "Enter number of test cases: "; cin >> t; for (int i = 0; i < t; i++) { cout << "Enter n, number of elements: "; cin >> n; vector<int> a; cout << "Enter elements: "; for (int j = 0; j < n; j++) { cin >> item; a.push_back(item); } if (equalsubset(a, n)) cout << "YES\n"; else cout << "NO\n"; } return 0; }

**Output**

Enter number of test cases: 2 Enter n, number of elements: 5 Enter elements: 3 4 6 2 5 YES Enter n, number of elements: 6 Enter elements: 1 3 4 8 5 6 NO

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.