Interview Question #6 Identical Subsets

Artyum Sirshenko
Jun 13 · 2 min read

This problem was asked by Facebook

“ Given a multiset of integers, return whether it can be partitioned into two subsets whose sums are the same. For example, given the multiset {15, 5, 20, 10, 35, 15, 10}, it would return true, since we can split it up into {15, 5, 10, 15, 10} and {20, 35}, which both add up to 55. Given the multiset {15, 5, 20, 10, 35}, it would return false, since we can’t split it up into two subsets that add up to the same sum. ”

The simplest approach I can think of to tackle this problem is first to think about the total sum of the values in the set. After we know the sum, we know the sum of each of the subsets, sum / 2. After we have the desirable sum for each subset, we can now start to check our set.

To start checking our set we will sort it first from largest to smallest and then start iterate through each of the values and adding it to our sum until we get to our subset sum which is sum / 2.

So if our sorted set is:

[35, 20, 15 ,15, 10, 10, 5] 

the sum is:

35 + 20 + 15 + 15 + 10 + 10 + 5 = 110

and our sum / 2 = 55

Means we need each subset sum will be equal 55. So we start at 35 and add it to the next value 20 and in this example, we done! 35 + 20 = 55 therefore, the rest of values will be also equal 55 and there is our 2 equal subsets (:

In other examples we will write more tests for each of the iterations such as, what we will do if the current sum + next item is > then subset? Well, in this case we will push this value to the second subset, and we will move on the the next value.

And what if the sum isn’t dividable by 2? Well, in this case the subset can’t be divided to equal subsets so we can simply return.

And what if we iterated through all the values and we still can’t get it equal to our subset sum? Well, in this case as well there is no solution.

Let’s code!

Artyum Sirshenko

Written by

Developer by day, Aspire engineer by night. https://github.com/obiwankenoobi