Interview Question #6 Identical Subsets

“ 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!

Written by