Partition Equal Subset 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 sounds easy until you count the possible splits. The problem is known as "Partition Equal Subset Sum", and it shows up at companies like Amazon and Facebook. It tests whether you can turn a partition question into a subset sum question, and then solve that without trying every subset.
TL;DR
Compute the total sum of the array. If the total is odd, return false. Otherwise, look for a subset that sums to half the total. Keep a set of every sum that some subset of the numbers seen so far can make, starting with {0} for the empty subset. For each number, build a new set from every old sum and every old sum plus the number. At the end, return whether half the total is in the set. This runs in O(n * S) time and O(S) space, where S is the sum of the absolute values of the numbers.
Prefer a different language? Jump to solutions in other languages.
Why This Problem Matters
The equal partition problem combines a mathematical reduction with dynamic programming. Interviewers like it because it tests three skills at once. You must see that an equal split is subset sum in disguise. You must notice that trying every subset is exponential. And you must find a state small enough to track: the set of sums reached so far.
Understanding the Problem
You are given an array of integers. Return true if you can split it into two subsets with the same sum, and false otherwise.
Every number goes into exactly one of the two subsets. The subsets do not need the same number of elements. A subset may be empty, and then its sum is 0. The numbers may be negative.
Constraints:
- The array has 1 to 50 numbers.
- Each number is between -1000 and 1000.
Here are the examples from the problem:
evenSplit([1,2,3,4,5,7]) -> true
4 and 7 sum to 11. The other numbers, 1, 2, 3 and 5, also sum to 11.
evenSplit([7,3,-10]) -> true
The array sums to 0. The empty subset and the whole array both sum to 0, so that split works.
evenSplit([1,2,3,4,5]) -> false
The total is 15, which is odd. An odd total cannot split into two equal integers.
Edge Cases
- Single element:
[0]returns true (split into[0]and[]), but[1]returns false. - Odd total sum: return false at once, with no search.
- Negative numbers:
[7,3,-10]sums to 0, so the empty subset works. Subset sums can also be negative, so the set must accept sums below 0. - Repeated values:
[2,2]is true,[2,2,1]is false.
The Key Insight: Reduction to Subset Sum
Reframe the question. If the total sum of the array is S, each subset of an equal split must sum to S/2. That is only possible when S is even. Once the parity check passes, the problem becomes: "Does any subset of the array sum to S/2?" If one subset sums to S/2, the numbers left out sum to the other S/2.
Here is how that reduction plays out for a small array, [1,2,3,4]:
Loading visualization...
When the total is odd, we return false right away:
Loading visualization...
The parity check costs one division after the sum, and it rules out every odd total before any real work.
Solution Approach
With the reduction in hand, we need a way to solve subset sum. Trying every subset means 2^n choices, which is far too many for 50 numbers. Many different subsets give the same sum, though. The sums are bounded: they range between the sum of the negative numbers and the sum of the positive numbers. So we track the set of reachable sums instead of the subsets themselves.
- Compute the total. If it is odd, return false.
- Set target = total / 2.
- Start the set of sums with 0. The empty subset makes 0.
- Process each number. Copy the set. For every sum
sin the old set, adds + numto the copy. Then replace the set with the copy. - Check the target. Return whether the target is in the set.
The copy matters. A sum in the copy either skips the current number (the old sum) or uses it once (the old sum plus the number). If we added to the same set while looping over it, a sum made with num could get num added again, so one number would count twice.
Building the Set of Sums
Here is the set for [1,2,3,4] with target 5. Each step adds one number:
Loading visualization...
After the last number the set contains every sum from 0 to 10. The target 5 is in the set, so the answer is true. One subset that makes 5 is {2,3}, and the rest, {1,4}, also makes 5.
The Negative-Number Example
The [7,3,-10] example is worth a separate trace. The total is 0, so the target is also 0. The set grows into negative sums when -10 arrives:
Loading visualization...
The target 0 is in the set from the start, because the empty subset makes 0. The answer is true.
Implementation
Here is the Java solution:
import java.util.Arrays;
public class Solution {
/**
* Tests if the array can be split into two
* with equal sum.
*
* @param input Input array.
* @return True if such a split is possible, false otherwise.
*/
public Boolean evenSplit(int[] input) {
int total = Arrays.stream(input).sum();
if (total % 2 != 0) return false;
int target = total / 2;
java.util.Set<Integer> sums = new java.util.HashSet<>();
sums.add(0);
for (int num : input) {
java.util.Set<Integer> nextSums = new java.util.HashSet<>(sums);
for (int s : sums) nextSums.add(s + num);
sums = nextSums;
}
return sums.contains(target);
}
}
How the method works:
total % 2 != 0: an odd total cannot split evenly, so the method returns false.sums.add(0): the empty subset makes 0, so the set starts with it.nextSums = new HashSet<>(sums): the copy keeps every old sum, which covers the choice to skipnum.nextSums.add(s + num): each old sum plusnumcovers the choice to usenumonce.sums.contains(target): after every number, the method checks whether some subset reaches half the total.
A HashSet accepts negative sums with no extra work, which matters for inputs like [7,3,-10].
Complexity Analysis
Let S be the sum of the absolute values of the numbers. Every subset sum lies between the sum of the negative numbers and the sum of the positive numbers, so the set never has more than S + 1 sums. With up to 50 numbers between -1000 and 1000, S is at most 50,000.
Time Complexity: O(n * S)
For each of the n numbers, the method copies the set and loops over it once. Each pass touches at most S + 1 sums, so the total work is O(n * S).
Space Complexity: O(S)
The method keeps two sets at a time, the current set and its copy. Each has at most S + 1 sums, so the space is O(S).
Why Not Try Every Subset?
A recursive search that includes or skips each number explores up to 2^n paths. For n = 50, that is over 10^15. The set of sums avoids this because two subsets with the same sum lead to the same future. The set stores that sum once, however many subsets reach it.
Common Pitfalls
- Forgetting the parity check. An odd total can never split evenly. Without the check,
total / 2rounds and the method can report a wrong true. - Adding to the set while looping over it. This lets one number count twice, and in Java it also throws a
ConcurrentModificationException. Build the new sums in a copy. - Leaving 0 out of the starting set. The empty subset makes 0. Without it,
[7,3,-10]returns false. - Indexing a boolean array by sum. A sum can be negative here. An array version must shift every index by the sum of the negative numbers, as the C++ solution does.
Interview Tips
- State the reduction clearly. "If the total is S, I need a subset that sums to S/2. This is subset sum." Interviewers want to see that you recognized the reduction.
- Check parity first. It is a one-line check that rules out impossible inputs before any real work.
- Explain why the state is small. Many subsets share a sum, and the sums are bounded by S. That is why tracking sums beats tracking subsets.
- Mention negative numbers. Say up front that a set, or an offset array, handles sums below 0.
- Trace a small example. Build the set for
[1,2,3,4]with target 5 before you write code.
Practice and Related Problems
This problem opens a family of subset and partition problems. Once you are comfortable with the set of reachable sums, try these:
- Subset Summation (Problem 97) tests the pure subset sum variant without the partition wrapper.
- Step Combinations to Reach the Summit (Problem 217) builds an answer one step at a time from earlier results, much like the set of sums here.
- Power Set Exploration (Problem 225) generates all subsets, which is the exhaustive search this approach avoids.
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, fluency with subset sum and its reachable-sums pattern will serve you well.
Solutions in Other Languages
Python
from typing import List
class Solution:
def even_split(self, input_list: List[int]) -> bool:
"""
Tests if the list can be split into two with equal sum.
:param input_list: Input list.
:return: True if such a split is possible, False otherwise.
"""
total = sum(input_list)
if total % 2 != 0:
return False
target = total // 2
sums = {0}
for num in input_list:
next_sums = set(sums)
for s in sums:
next_sums.add(s + num)
sums = next_sums
return target in sums
JavaScript
class Solution {
/**
* Tests if the array can be split into two
* with equal sum.
*
* @param {Array<number>} input Input array.
* @return {boolean} True if such a split is possible, false otherwise.
*/
evenSplit(input) {
const total = input.reduce((a, b) => a + b, 0);
if (total % 2 !== 0) return false;
const target = total / 2;
let sums = new Set([0]);
for (const num of input) {
const nextSums = new Set(sums);
for (const s of sums) nextSums.add(s + num);
sums = nextSums;
}
return sums.has(target);
}
}
module.exports = Solution;
TypeScript
class Solution {
/**
* Tests if the array can be split into two
* with equal sum.
*
* @param input - Input array.
* @returns True if such a split is possible, false otherwise.
*/
evenSplit(input: number[]): boolean {
const total = input.reduce((a, b) => a + b, 0);
if (total % 2 !== 0) return false;
const target = total / 2;
let sums = new Set<number>([0]);
for (const num of input) {
const nextSums = new Set(sums);
for (const s of sums) nextSums.add(s + num);
sums = nextSums;
}
return sums.has(target);
}
}
export { Solution };
C++
The C++ solution uses a std::vector<bool> in place of a hash set. Index s - low stands for sum s, where low is the sum of the negative numbers. The vector has high - low + 1 entries, which is at most S + 1.
#include <iostream>
#include <vector>
#include <numeric>
class Solution {
public:
/**
* Tests if the array can be split into two
* with equal sum.
*
* @param input Input array.
* @return True if such a split is possible, false otherwise.
*/
bool evenSplit(std::vector<int> &input) {
int total = std::accumulate(input.begin(), input.end(), 0);
if (total % 2 != 0) return false;
int target = total / 2;
int low = 0, high = 0;
for (int num : input) {
if (num < 0) low += num;
else high += num;
}
std::vector<bool> sums(high - low + 1, false);
sums[-low] = true;
for (int num : input) {
std::vector<bool> nextSums = sums;
for (int s = low; s <= high; s++) {
if (sums[s - low]) nextSums[s + num - low] = true;
}
sums = nextSums;
}
return sums[target - low];
}
};
Go
Go has no built-in set, so the solution uses a map[int]bool. The inner loop puts both the old sum and the old sum plus num into the new map.
package solution
// You can import standard packages below, like "fmt" and "strings":
// EvenSplit checks if an array can be split into two
// with equal sum.
func (s *Solution) EvenSplit(input []int) bool {
total := 0
for _, num := range input {
total += num
}
if total%2 != 0 {
return false
}
target := total / 2
sums := map[int]bool{0: true}
for _, num := range input {
nextSums := make(map[int]bool, len(sums)*2)
for s := range sums {
nextSums[s] = true
nextSums[s+num] = true
}
sums = nextSums
}
return sums[target]
}
// Solution is required to run your method. Do not modify.
type Solution struct {
}
Scala
class Solution {
/**
* Tests if the array can be split into two
* with equal sum.
*
* @param input Input array.
* @return True if such a split is possible, false otherwise.
*/
def evenSplit(input: Array[Int]): Boolean = {
val total = input.sum
if (total % 2 != 0) return false
val target = total / 2
var sums = scala.collection.mutable.HashSet(0)
for (num <- input) {
val nextSums = sums.clone()
for (s <- sums) nextSums += s + num
sums = nextSums
}
sums.contains(target)
}
}
Kotlin
class Solution {
/**
* Tests if the array can be split into two
* with equal sum.
*
* @param input Input array.
* @return True if such a split is possible, false otherwise.
*/
fun evenSplit(input: IntArray): Boolean {
val total = input.sum()
if (total % 2 != 0) return false
val target = total / 2
var sums = hashSetOf(0)
for (num in input) {
val nextSums = HashSet(sums)
for (s in sums) nextSums.add(s + num)
sums = nextSums
}
return target in sums
}
}
Swift
class Solution {
/**
* Tests if the array can be split into two
* with equal sum.
*
* - Parameter input: Input array.
* - Returns: True if such a split is possible, false otherwise.
*/
func evenSplit(_ input: [Int]) -> Bool {
let total = input.reduce(0, +)
if total % 2 != 0 { return false }
let target = total / 2
var sums: Set<Int> = [0]
for num in input {
var nextSums = sums
for s in sums { nextSums.insert(s + num) }
sums = nextSums
}
return sums.contains(target)
}
}
Rust
pub struct Solution;
impl Solution {
/// Tests if the array can be split into two
/// with equal sum.
///
/// # Arguments
/// * `input` - Input array
///
/// # Returns
/// True if such a split is possible, false otherwise
pub fn even_split(&self, input: Vec<i32>) -> bool {
let total: i32 = input.iter().sum();
if total % 2 != 0 {
return false;
}
let target = total / 2;
let mut sums = std::collections::HashSet::from([0]);
for &num in &input {
let mut next_sums = sums.clone();
for &s in &sums {
next_sums.insert(s + num);
}
sums = next_sums;
}
sums.contains(&target)
}
}
Firecode's Rust runner imports HashSet for you. To compile the code on its own, add use std::collections::HashSet; at the top.
Dart
class Solution {
/// Tests if the array can be split into two
/// with equal sum.
///
/// [input] Input array.
/// Returns true if such a split is possible, false otherwise.
bool evenSplit(List<int> input) {
int total = input.fold(0, (a, b) => a + b);
if (total % 2 != 0) return false;
int target = total ~/ 2;
Set<int> sums = {0};
for (int num in input) {
Set<int> nextSums = Set<int>.of(sums);
for (int s in sums) nextSums.add(s + num);
sums = nextSums;
}
return sums.contains(target);
}
}
C#
using System.Linq;
public class Solution {
/// <summary>
/// Tests if the array can be split into two
/// with equal sum.
/// </summary>
/// <param name="input">Input array.</param>
/// <returns>True if such a split is possible, false otherwise.</returns>
public bool EvenSplit(int[] input) {
int total = input.Sum();
if (total % 2 != 0) return false;
int target = total / 2;
var sums = new System.Collections.Generic.HashSet<int> { 0 };
foreach (int num in input) {
var nextSums = new System.Collections.Generic.HashSet<int>(sums);
foreach (int s in sums) nextSums.Add(s + num);
sums = nextSums;
}
return sums.Contains(target);
}
}
Ruby
The Ruby solution uses a hash as the set, with each sum as a key.
class Solution
# Tests if the array can be split into two with equal sum.
#
# @param input [Array<Integer>] Input array.
# @return [Boolean] True if such a split is possible, false otherwise.
def even_split(input)
total = input.sum
return false if total.odd?
target = total / 2
sums = { 0 => true }
input.each do |num|
next_sums = sums.dup
sums.each_key { |s| next_sums[s + num] = true }
sums = next_sums
end
sums.key?(target)
end
private
end
PHP
The PHP solution uses an array as the set, with each sum as a key. intdiv keeps the target an integer.
<?php
class Solution {
/**
* Tests if the array can be split into two
* with equal sum.
*
* @param array $input Input array.
* @return bool True if such a split is possible, false otherwise.
*/
public function evenSplit(array $input): bool {
$total = array_sum($input);
if ($total % 2 !== 0) {
return false;
}
$target = intdiv($total, 2);
$sums = [0 => true];
foreach ($input as $num) {
$nextSums = $sums;
foreach (array_keys($sums) as $s) {
$nextSums[$s + $num] = true;
}
$sums = $nextSums;
}
return isset($sums[$target]);
}
}