Press "Enter" to skip to content

How to find whether an array can be divided into two equal-sum parts

Ajk 5

When I first saw this question I got quite intrigued and a bit #mindflabergasted. This sounds like something you could get asked on interviews. A very interesting question that can give quite a lot of insight about how important requirements and clear understanding of the problem can be.

Well first off, let us start with specifications and ambiguity as per usual. There’s a little dilemma in my head about the question. It can have to meanings:

  1. Find whether the array can be divided AS-IS, in that exact order into two equal-sum parts?
  2. Find whether the array can be divided in two equal-sum parts, independent of ordering, (meaning, whether you can find two subsets of the array that are of equal sum)

For the sake of developing our solution we will try to solve both and we will see how a small assumption early on, of one or the other, can lead to a totally different thought process, solution and, hence mistake if our interviewer was asking us the other one.

Find whether the array can be divided AS-IS, in that exact order into two equal-sum parts?

This should not be that hard, should it? So for the array to be divisible into two equal-sum parts in the same order, we need to have a point in the array where the subset to the left of that point will equal to the subset to the right and will equal to half of the total sum of the array.
Hence we can come up with an algorithm like this:

  1. Find the total sum of all elements in the array
  2. If sum is an odd number, return, the array cannot get divided
  3. Otherwise, go through the array keeping a left sum, until left sum is equal to half of the total sum

Sounds great! A quick analysis of the worst case scenario will give us:

  • Time Complexity – Go through the list twice – O(n)
  • Space Complexity – Keep a few variables – O(1)

Now let’s head into some easy coding and get this going. We’ll be using Java as per usual:

Looks great! Can we improve? There does not seem to be a way to save on Time Complexity (O(n)) or Space Complexity (O(1)), but maybe we can imrpove something stylistically.
Let’s give it another try and make the code more readable.

Now our overall code is slightly longer, but the main method we wrote in Java is a lot shorter and a lot more readable. Indeed, I do not think we need the comments anymore, as someone just reading the code will probably understand exactly what is happening. Furthermore we have put different levels of abstraction in different methods, so our main one only shows a higher level understanding of the problem.

Sounds great, so now let us tackle the second problem…

Find whether the array can be divided in two equal-sum subsets, independent of ordering

Well if you followed me so far, you will probably think that this is going to be just straight forward generalization of the problem we were looking at before.

You know what, I am going to leave you with this for a few hours, see if you can come up with something. Remember all work is good work, even the one that does not lead to the correct result ;). Let me know your thoughts and solutions for this part!

EDIT: As someone stated below the best approach in this case (and IMO in a lot of cases where you have a to deal with subsets (i.e. n choose k)), is dynamic algorithm. So the idea behind it is fairly simple. The execution is a bit harder. The idea is we will have a 2D array with the array Size on one axis and the possible halfSum on the other. On each cell we will know if for that array size we can reach target number (in the half sum axis).

Here you have a piece of code that I came up with while trying to come up with a solution:

I ran it a few times and it seems to work flawlessly.

Hope you guys enjoyed it… and I’ll see you guys next time ;D

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂