Partition Equal Subset Sum

AS
Ackshaey Singh
Difficulty Hard
Time Complexity
O(n * S)
Space Complexity
O(S)
Dynamic Programming Recursion Array
Amazon Facebook

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

  1. Single element: [0] returns true (split into [0] and []), but [1] returns false.
  2. Odd total sum: return false at once, with no search.
  3. 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.
  4. 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.

  1. Compute the total. If it is odd, return false.
  2. Set target = total / 2.
  3. Start the set of sums with 0. The empty subset makes 0.
  4. Process each number. Copy the set. For every sum s in the old set, add s + num to the copy. Then replace the set with the copy.
  5. 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 skip num.
  • nextSums.add(s + num): each old sum plus num covers the choice to use num once.
  • 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

  1. Forgetting the parity check. An odd total can never split evenly. Without the check, total / 2 rounds and the method can report a wrong true.
  2. 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.
  3. Leaving 0 out of the starting set. The empty subset makes 0. Without it, [7,3,-10] returns false.
  4. 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

  1. 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.
  2. Check parity first. It is a one-line check that rules out impossible inputs before any real work.
  3. 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.
  4. Mention negative numbers. Say up front that a set, or an offset array, handles sums below 0.
  5. 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]);
    }
}

Frequently Asked Questions

What is the partition equal subset sum problem?
The partition equal subset sum problem asks whether an array of integers can be split into two subsets with the same sum. Every number goes into exactly one subset. It reduces to finding a subset that sums to half the array total. If the total is odd, the answer is false.
How does the set of reachable sums solve the problem?
First compute the total. If it is odd, return false. Otherwise set the target to half the total and start a set with 0, the sum of the empty subset. For each number, copy the set and add every old sum plus the number to the copy, then replace the set with the copy. At the end, return whether the target is in the set.
What is the time complexity of the solution?
The time complexity is O(n * S), where n is the number of elements and S is the sum of their absolute values. Every subset sum lies in a range of at most S + 1 values, so each of the n passes touches at most S + 1 sums. With 50 numbers between -1000 and 1000, S is at most 50,000.
What is the space complexity of the solution?
The space complexity is O(S). The method keeps the current set of sums and one copy, and each has at most S + 1 sums.
Why copy the set before adding new sums?
The copy keeps each number from counting twice. Every sum in the copy either skips the current number or uses it once. If new sums went into the same set during the loop, a sum that already used the number could get it added again. In Java, changing a HashSet while looping over it also throws a ConcurrentModificationException.
Why check whether the total sum is odd first?
An odd total cannot split into two equal integers. Without the check, integer division rounds the target down and the method can return a wrong true. For [1], the target would round to 0, and 0 is always reachable through the empty subset.
How does the solution handle negative numbers?
A subset sum can be negative, so the set must accept sums below 0. A hash set does this with no extra work. The C++ solution uses a boolean vector instead and shifts each index by the sum of the negative numbers, so index 0 stands for the smallest possible sum.
Why not try every subset with recursion?
A recursive search that includes or skips each number explores up to 2^n paths, which is over 10^15 for 50 numbers. Many subsets share the same sum, and the set stores each sum once. That brings the work down to O(n * S).
How does this problem relate to the subset sum problem?
The equal partition problem is a direct reduction to subset sum. If the array total is S, an equal split means a subset that sums to S/2. The numbers left out then sum to S/2 as well. Any subset sum method can solve this problem.
What edge cases should I consider?
Key edge cases include a single-element array (false unless the element is 0), an array whose total is 0 so the empty subset works, negative numbers that push subset sums below 0, and repeated values such as [2,2] (true) and [2,2,1] (false).