Split array with equal sum

You are in the middle of an Amazon phone screen. The interviewer says, "I have an array of integers. Can you tell me if it is possible to split it into two groups that have the same sum?" This is one of those problems that sounds straightforward until you start thinking about the number of possible splits. It is also known as "Partition Equal Subset Sum" on other platforms, and it shows up regularly at companies like Amazon and Facebook because it tests whether a candidate can recognize a classic reduction: turning a partition question into a subset sum search.

TL;DR

Compute the total sum of the array. If the sum is odd, return false immediately. Otherwise, use recursion to search for any subset that sums to half the total. At each index, branch into two choices: include the element (subtract it from the target) or exclude it (leave the target unchanged). If the target reaches 0, the partition exists. This runs in O(2^n) time and O(n) space from the recursion stack.

Prefer a different language? Jump to solutions in other languages.

Why This Problem Matters

The equal partition problem sits at the intersection of recursion and combinatorial search. Interviewers love it because it tests three skills at once: recognizing a mathematical reduction, implementing recursive backtracking, and reasoning about exponential time complexity. Once you see that partitioning into equal halves is just subset sum in disguise, you have the key insight. From there, the code writes itself.

Understanding the Problem

Given an array of n integers, determine whether you can split it into two halves with equal sum. The halves do not need to have the same length, and either half can be empty (an empty sub-array has sum 0).

Here is the example from the problem:

evenSplit([1,2,3,4]) -> true

We can split [1,2,3,4] into [2,3] and [1,4]. Both groups sum to 5.

evenSplit([7,3,-10]) -> true

This one is less obvious. The array sums to 0, so both [] and [7,3,-10] have sum 0. An empty sub-array is a valid half.

evenSplit([1,2,4]) -> false

The total sum is 7, which is odd. No way to split an odd total into two equal integers.

Edge Cases

1. Single element: [0] returns true (split into [0] and []), but [1] returns false.
2. Odd total sum: Immediately false, no recursion needed.
3. Negative numbers: [7,3,-10] sums to 0, so the empty subset works.
4. All same values: [2,2] is true, [2,2,1] is false.

The Key Insight: Reduction to Subset Sum

The trick is to reframe the question. If the total sum of the array is S, splitting it into two halves with equal sum means each half must sum to S/2. That is only possible when S is even. Once you check parity, the problem becomes: "Does any subset of the array sum to S/2?"

Here is how that reduction plays out for [1,2,3,4]:

And when the sum is odd, we short-circuit immediately:

This parity check is cheap (constant time) and eliminates half of all possible inputs before we do any real work.

Solution Approach

With the reduction in hand, we need a method to solve subset sum. The recursive approach is the most natural fit:

1. Compute the total sum. If odd, return false.
2. Set target = sum / 2.
3. Recurse through the array. At each index, try two paths:
   • Include the current element: subtract it from the target and advance the index.
   • Exclude the current element: keep the target unchanged and advance the index.
4. Base cases:
   • If the target reaches 0, return true (we found a valid subset).
   • If we have exhausted all elements without hitting 0, return false.

Recursion Tree

Let's visualize the recursive search for [1,2,3,4] with target 5. Each node shows the current index and remaining target. Left branches include the element, right branches exclude it. Highlighted nodes mark the successful path:

The search finds that excluding 1, including 2, and including 3 produces target = 5 - 2 - 3 = 0. Once that branch returns true, the recursion unwinds and reports success.

Notice that the tree is pruned here for clarity. In the worst case every branch expands fully, giving 2^n leaf nodes.

The Zero-Sum Edge Case

The [7,3,-10] example is worth tracing separately. The total is 0, so the target is also 0. The helper method hits the early exit on its very first call:

No recursion needed at all. The early exit handles this in constant time.

Implementation

Here is the Java solution:

import java.util.Arrays;

public class Solution {
  public Boolean evenSplit(int[] input) {
    int sum = Arrays.stream(input).sum();

    if (sum % 2 != 0) return false;

    return search(input, 0, sum / 2);
  }

  private Boolean search(int[] input, int index, int target) {
    if (index == input.length) return target == 0;

    else if (target == 0) return true;

    else return search(input, index + 1, target - input[index]) ||
                  search(input, index + 1, target);
  }
}

Walk through the helper method:

• index == input.length: We have processed every element. If the target is exactly 0, we found a valid subset. Otherwise we haven't.
• target == 0: Early exit. A valid subset was found before we even finished scanning the array.
• Recursive case: Try including the current element (subtract from target) OR excluding it (leave target alone). The || short-circuits on the first true result.

Complexity Analysis

Time Complexity: O(2^n)

At each of the n elements we make two choices: include or exclude. This creates a binary tree of decisions with up to 2^n leaves. For n = 50, that is over 10^15 nodes, which is far too large to explore exhaustively. In practice, the early exit when target reaches 0 prunes most branches, making the recursive approach viable for many inputs. However, this is best viewed as a conceptual baseline that illustrates the include/exclude pattern. A DP optimization (discussed below) is necessary for worst-case efficiency.

Space Complexity: O(n)

The recursion stack can go n levels deep (one level per array element). No auxiliary data structures are allocated beyond the stack frames themselves.

Could We Do Better?

Yes. A dynamic programming approach using a boolean array of size target + 1 brings the time down to O(n * target). For each element, iterate backward through the DP array and mark newly reachable sums. Note that this DP formulation assumes non-negative values (the target and all reachable sums are non-negative). For arrays with negative numbers, you would need a hash set of reachable sums or index offsetting. This DP optimization is worth mentioning in an interview as a follow-up, but the recursive solution demonstrates the core insight cleanly.

Common Pitfalls

1. Forgetting the parity check. Without it, you waste time recursing on inputs that can never produce a valid split.
2. Missing the empty-subset case. An empty sub-array sums to 0, which is a valid half if the full array also sums to 0.
3. Integer overflow on large sums. The constraints here are small (values between -1000 and 1000, n up to 50), so overflow is not a concern, but always verify constraints.
4. Not short-circuiting on target == 0. Without the early exit, the recursion explores unnecessary branches after already finding a valid subset.

Interview Tips

1. State the reduction clearly. "If the total sum is S, I need to find a subset that sums to S/2. This is subset sum." Interviewers want to see that you recognized the reduction.
2. Check parity first. It is a one-line check that shows you think about eliminating impossible cases before doing heavy computation.
3. Mention the DP follow-up. Even if you implement the recursive version, say "This could be optimized to O(n * target) with DP." It signals awareness of the full solution space.
4. Trace a small example. Walk through [1,2,3,4] with target 5 to demonstrate your solution works before coding.

Practice and Related Problems

This problem is a gateway to a family of subset and partition problems. Once you are comfortable with the recursive subset sum approach, try these:

• Subset Summation (Problem 97) tests the pure subset sum variant without the partition wrapper.
• Step Combinations to Reach the Summit (Problem 217) applies similar branching recursion to a counting problem.
• Power Set Exploration (Problem 225) generates all subsets, which is the exhaustive version of what we pruned here.

This problem and many more are available on Firecode, where over 50,000 engineers have prepared for technical interviews at top companies. Whether you are targeting Amazon, Facebook, or another top firm, building fluency with recursive search patterns like this one will serve you well.

Solutions in Other Languages

Python

from typing import List


class Solution:
    def even_split(self, input_list: List[int]) -> bool:
        list_sum = sum(input_list)

        if list_sum % 2 != 0:
            return False

        return self.search(input_list, 0, list_sum // 2)

    def search(self, input_list: List[int], index: int, target: int) -> bool:
        if index == len(input_list):
            return target == 0

        elif target == 0:
            return True

        else:
            return self.search(input_list, index + 1, target - input_list[index]) or \
                   self.search(input_list, index + 1, target)

JavaScript

class Solution {
  evenSplit(input) {
    const sum = input.reduce((n1, n2) => n1 + n2, 0);

    if (sum % 2 !== 0) return false;

    return this.search(input, 0, sum / 2);
  }

  search(input, index, target) {
    if (index === input.length) return target === 0;

    else if (target === 0) return true;

    else return this.search(input, index + 1, target - input[index]) ||
        this.search(input, index + 1, target);
  }
}

TypeScript

class Solution {
  evenSplit(input: number[]): boolean {
    const sum = input.reduce((n1, n2) => n1 + n2, 0);

    if (sum % 2 !== 0) return false;

    return this.search(input, 0, sum / 2);
  }

  search(input: number[], index: number, target: number): boolean {
    if (index === input.length) return target === 0;

    else if (target === 0) return true;

    else return this.search(input, index + 1, target - input[index]) ||
        this.search(input, index + 1, target);
  }
}

C++

#include <iostream>
#include <vector>
#include <numeric>

class Solution {
public:
  bool evenSplit(std::vector<int> &input) {
    int sum = std::accumulate(input.begin(), input.end(), 0);

    if (sum % 2 != 0) return false;

    return search(input, 0, sum / 2);
  }

private:
  bool search(std::vector<int> &input, int index, int target) {
    if (index == input.size()) return target == 0;

    else if (target == 0) return true;

    else {
      return search(input, index + 1, target - input[index]) ||
             search(input, index + 1, target);
    }
  }
};

Go

func (s *Solution) EvenSplit(input []int) bool {
    sum := 0
    for _, val := range input {
        sum += val
    }

    if sum%2 != 0 {
        return false
    }

    return search(input, 0, sum/2)
}

func search(input []int, index int, target int) bool {
    if index == len(input) {
        return target == 0
    } else if target == 0 {
        return true
    } else {
        return search(input, index+1, target-input[index]) ||
            search(input, index+1, target)
    }
}

Scala

class Solution {
  def evenSplit(input: Array[Int]): Boolean = {
    val sum = input.sum

    if (sum % 2 != 0) return false

    search(input, 0, sum / 2)
  }

  private def search(input: Array[Int], index: Int, target: Int): Boolean = {
    if (index == input.length) target == 0

    else if (target == 0) true

    else search(input, index + 1, target - input(index)) ||
      search(input, index + 1, target)
  }
}

Kotlin

class Solution {
  fun evenSplit(input: IntArray): Boolean {
    val sum = input.sum()

    if (sum % 2 != 0) return false

    return search(input, 0, sum / 2)
  }

  private fun search(input: IntArray, index: Int, target: Int): Boolean {
    if (index == input.size) return target == 0

    else if (target == 0) return true

    else return search(input, index + 1, target - input[index]) ||
                search(input, index + 1, target)
  }
}

Swift

class Solution {
    func evenSplit(_ input: [Int]) -> Bool {
        let sum = input.reduce(0, +)

        if sum % 2 != 0 { return false }

        return search(input, 0, sum / 2)
    }

    private func search(_ input: [Int], _ index: Int, _ target: Int) -> Bool {
        if index == input.count { return target == 0 }

        else if target == 0 { return true }

        else {
            return search(input, index + 1, target - input[index]) ||
                   search(input, index + 1, target)
        }
    }
}

Rust

impl Solution {
    pub fn even_split(&self, input: Vec<i32>) -> bool {
        let sum: i32 = input.iter().sum();

        if sum % 2 != 0 {
            return false;
        }

        self.search(&input, 0, sum / 2)
    }

    fn search(&self, input: &[i32], index: usize, target: i32) -> bool {
        if index == input.len() {
            return target == 0;
        }

        if target == 0 {
            return true;
        }

        self.search(input, index + 1, target - input[index]) ||
            self.search(input, index + 1, target)
    }
}

Dart

class Solution {
  bool evenSplit(List<int> input) {
    int sum = input.fold(0, (a, b) => a + b);

    if (sum % 2 != 0) return false;

    return _search(input, 0, sum ~/ 2);
  }

  bool _search(List<int> input, int index, int target) {
    if (index == input.length) return target == 0;

    else if (target == 0) return true;

    else return _search(input, index + 1, target - input[index]) ||
                _search(input, index + 1, target);
  }
}

C#

using System.Linq;

public class Solution {
    public bool EvenSplit(int[] input) {
        int sum = input.Sum();

        if (sum % 2 != 0) return false;

        return Search(input, 0, sum / 2);
    }

    private bool Search(int[] input, int index, int target) {
        if (index == input.Length) return target == 0;

        else if (target == 0) return true;

        else return Search(input, index + 1, target - input[index]) ||
                    Search(input, index + 1, target);
    }
}

Ruby

class Solution
  def even_split(input)
    array_sum = input.sum

    return false if array_sum.odd?

    search(input, 0, array_sum / 2)
  end

  private

  def search(input, index, target)
    return target == 0 if index == input.length

    return true if target.zero?

    search(input, index + 1, target - input[index]) || search(input, index + 1, target)
  end
end

PHP

class Solution {
    public function evenSplit(array $input): bool {
        $sum = array_sum($input);

        if ($sum % 2 !== 0) {
            return false;
        }

        return $this->search($input, 0, $sum / 2);
    }

    private function search(array $input, int $index, int $target): bool {
        if ($index === count($input)) {
            return $target === 0;
        }

        if ($target === 0) {
            return true;
        }

        return $this->search($input, $index + 1, $target - $input[$index]) ||
               $this->search($input, $index + 1, $target);
    }
}