Partition Equal Subset Sum

Partition Equal Subset Sum looks like a puzzle about splitting numbers. But the interviewer is really checking one thing. Can you spot a hidden knapsack problem when it is wearing a disguise? Once you see the disguise, the whole thing becomes easy.

🎯 The Problem

You get an array of positive numbers and you decide if it can split into two equal-sum groups.

• Both groups must have the same total.
• You do not return the groups. You return true or false.
• The target you aim for is half the total of all numbers.
• If a subset reaches the target, the rest reaches it too, so both halves match.

For [1, 5, 11, 5], the total is 22 and half is 11. Can you pick numbers that add up to exactly 11? Yes, 11 alone makes one group and 1 + 5 + 5 makes the other. So the answer is true.

Input:  nums = [1, 5, 11, 5]
Output: true

Explanation: [11] and [1, 5, 5] both add up to 11

One quick check first. If the total is an odd number, you can never split it evenly. So the answer is false right away.

Here is the problem as a picture. We split one array into two equal-sum groups.

🐢 Approach 1: Plain Recursion (Brute Force)

Try every subset by taking or leaving each number.

The idea:

• For each number you take it into your group or leave it out.
• Walk down the array one number at a time, branching into two paths.

How it works:

• Carry a running goal, starting at the target.
• Take a number, subtract it from the goal. Leave it, the goal stays.
• If the goal hits zero, a subset works, so return true.
• Run out of numbers with the goal above zero, that path failed.

Why it is weak:

• Each number doubles the number of paths.
• The time is O(2ⁿ), very slow for big arrays.

Here is the plain recursion code:

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2

    def dfs(index, current):
        if current == target:
            return True
        if index == len(nums) or current > target:
            return False
        return dfs(index + 1, current + nums[index]) or dfs(index + 1, current)

    return dfs(0, 0)

⚡ Approach 2: Memoization (Better)

Save each (index, remaining goal) pair so it is solved only once.

The idea:

• Many branches reach the same situation: same index, same remaining goal.
• The plain version solves each from scratch. That is wasted work.

How it works:

• Keep a table keyed by the pair of index and remaining goal.
• The first time you solve a pair, save the result.
• Next time the same pair shows up, read the saved answer.

Why it is fast:

• Each distinct pair runs once.
• Time drops to about O(n × target).

Here is the memoized recursion:

from functools import lru_cache


def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2

    @lru_cache(None)
    def dfs(index, current):
        if current == target:
            return True
        if index == len(nums) or current > target:
            return False
        return dfs(index + 1, current + nums[index]) or dfs(index + 1, current)

    return dfs(0, 0)

⚡ Approach 3: Bottom-Up Tabulation (Better)

Build a 2D true/false grid from the smallest cases up.

The idea:

• One side is which numbers we are allowed to use.
• The other side is every possible sum from zero up to the target.
• A cell dp[i][s] asks: using the first i numbers, can we reach the sum s?

How it works:

• Fill the grid row by row.
• Each cell looks at the cell above it.
• Tabulation fills in order so every cell already has the answers it depends on.

Why it is fine:

• No recursion stack, only loops.
• The final cell tells us if the target is reachable. Time is O(n × target).

Here is the grid filling for [1, 5, 11, 5] with target 11. Each row adds one more number. A true cell means that sum is reachable so far.

🚀 Approach 4: Space-Optimized One Row (Best)

Keep one boolean row and update it in place.

The idea:

• Each row only reads the row directly above it.
• So the whole grid is never needed. One row is enough.

How it works:

• For each number, walk the sums from high to low.
• Low to high would reuse the same number twice in one step.
• High to low keeps each number used at most once.

Why it is best:

• This is the 0/1 knapsack trick, where each item is taken at most once.
• Time stays O(n × target), but memory drops to O(target).

Steps to Solve

1. Add up all numbers to get the total. If the total is odd, return false.
2. Set the target to half the total.
3. Make a boolean array dp of size target plus one. Set dp[0] to true, since sum zero is always reachable.
4. For each number, walk the sums from target down to that number.
5. For each sum s, set dp[s] to true if dp[s] was already true or dp[s - num] is true.
6. After all numbers, return dp[target].

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool canPartition(int nums[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) total += nums[i];
    if (total % 2 != 0) return false;   // odd total can never split evenly
    int target = total / 2;

    bool dp[10001];
    memset(dp, 0, sizeof(dp));
    dp[0] = true;                       // sum 0 is always reachable

    for (int i = 0; i < n; i++) {
        for (int s = target; s >= nums[i]; s--) {  // high to low
            if (dp[s - nums[i]]) dp[s] = true;
        }
    }
    return dp[target];
}

int main(void) {
    int nums[] = {1, 5, 11, 5};
    int n = 4;
    printf("%s\n", canPartition(nums, n) ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

bool canPartition(vector<int>& nums) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    if (total % 2 != 0) return false;   // odd total cannot split
    int target = total / 2;

    vector<bool> dp(target + 1, false);
    dp[0] = true;                       // sum 0 reachable

    for (int num : nums) {
        for (int s = target; s >= num; s--) {  // high to low
            if (dp[s - num]) dp[s] = true;
        }
    }
    return dp[target];
}

int main() {
    vector<int> nums = {1, 5, 11, 5};
    cout << (canPartition(nums) ? "true" : "false") << endl;
    return 0;
}

true

public class PartitionSubset {
    public static boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums) total += num;
        if (total % 2 != 0) return false;   // odd total cannot split
        int target = total / 2;

        boolean[] dp = new boolean[target + 1];
        dp[0] = true;                       // sum 0 reachable

        for (int num : nums) {
            for (int s = target; s >= num; s--) {  // high to low
                if (dp[s - num]) dp[s] = true;
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        int[] nums = { 1, 5, 11, 5 };
        System.out.println(canPartition(nums));
    }
}

true

def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0:            # odd total can never split evenly
        return False
    target = total // 2

    dp = [False] * (target + 1)
    dp[0] = True                  # sum 0 is always reachable

    for num in nums:
        for s in range(target, num - 1, -1):   # high to low
            if dp[s - num]:
                dp[s] = True
    return dp[target]


nums = [1, 5, 11, 5]
print(str(can_partition(nums)).lower())

true

function canPartition(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;   // odd total cannot split
  const target = total / 2;

  const dp = new Array(target + 1).fill(false);
  dp[0] = true;                        // sum 0 reachable

  for (const num of nums) {
    for (let s = target; s >= num; s--) {  // high to low
      if (dp[s - num]) dp[s] = true;
    }
  }
  return dp[target];
}

const nums = [1, 5, 11, 5];
console.log(canPartition(nums));

true

Let us walk through the Python version line by line, because the why behind each line is the real lesson.

total = sum(nums) adds every number. We need the total to know what half looks like.

if total % 2 != 0: return False is the early exit. An odd total can never break into two equal halves. So we stop right here.

target = total // 2 sets the goal. From now on we only ask one question. Can we reach this target with some subset?

dp = [False] * (target + 1) makes one row of answers. dp[s] will mean “sum s is reachable”. We start everything false.

dp[0] = True is the seed. A sum of zero is always reachable by picking nothing. Every other answer grows out of this one.

for num in nums: brings in one number at a time. Each loop is like adding one more row to the imagined grid.

for s in range(target, num - 1, -1): walks sums from high to low. This high-to-low order is the key. It stops us from using the same number twice in one pass.

if dp[s - num]: dp[s] = True is the transition. If sum s - num was already reachable, then by adding num we can now reach s. So we mark s true.

return dp[target] gives the final answer. If the target became reachable, the array can be split.

⏱️ Time and Space Complexity

Plain recursion explores a full tree of choices, so it is exponential. Memoization and tabulation both bring the time down to O(n times target), because there are only that many distinct subproblems. The space-optimized version keeps just one row, so it uses the least memory while staying just as fast.

🧩 Key Takeaways

• ✅ If the total is odd, the answer is false right away.
• ✅ The real question is whether some subset reaches half the total.
• ✅ Each number can be taken or left, which makes it a 0/1 knapsack.
• ✅ One rolling boolean row is enough if you walk sums from high to low.
• ✅ High to low order stops you from reusing the same number twice.

🚀 What’s Next?

• Coin Change 2
• Longest Common Subsequence