Problem statement

Given an integer array nums, return true if it can be partitioned into two subsets with equal sums.

Example 1

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

Example 2

Input: nums = [1,2,3,5]
Output: false

Constraints

• 1 <= nums.length <= 20
• 1 <= nums[i] <= 25

Hints for Partition Equal Subset Sum

1. Hint 1

   If the total sum is odd, it's impossible; otherwise look for a subset summing to total/2.

2. Hint 2

   0/1-knapsack over reachable sums — iterate amounts downward to use each number once.

How to solve Partition Equal Subset Sum

Two subsets with equal sums each hold exactly half the total, so the question reduces to: is some subset's sum equal to total / 2? That is a 0/1 subset-sum problem, answerable with a boolean table over reachable sums. An odd total is impossible outright.

Approach

1. Sum the array; if the total is odd, return false immediately.
2. Set target = total / 2 and create reachable[0 .. target] with only reachable[0] = true.
3. For each number x, sweep the sums downwards from target to x, setting reachable[a] |= reachable[a - x].
4. Return reachable[target].

Why it works

Picking a subset summing to half forces its complement to sum to half as well, so one subset determines both — the two-way partition question really is a one-way subset-sum question. The downward sweep is what makes it 0/1 rather than unbounded: iterating high to low means reachable[a - x] still reflects the state before x was considered, so each number is used at most once. Sweeping upwards would let a number be reused and answer a different problem.

Complexity

• Time — O(n · total)
• Space — O(total)

Pitfalls

• The downward sweep is essential; going upwards allows reusing an element and yields false positives.
• The odd-total shortcut is not just an optimisation — halving an odd number is meaningless.
• reachable[0] = true seeds everything: the empty subset sums to zero.
• All values are positive here, which is what makes the sum bound and the table size well defined.

Reference solution

Python

from typing import List

def canPartition(nums: List[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [True] + [False] * target
    for x in nums:
        for a in range(target, x - 1, -1):
            if dp[a - x]:
                dp[a] = True
    return dp[target]

Java

public static boolean canPartition(int[] nums) {
    int total = 0;
    for (int x : nums) total += x;
    if (total % 2 != 0) return false;
    int target = total / 2;
    boolean[] reachable = new boolean[target + 1];
    reachable[0] = true;
    for (int x : nums) {
        for (int a = target; a >= x; a--) {
            if (reachable[a - x]) reachable[a] = true;
        }
    }
    return reachable[target];
}

C++

bool canPartition(vector<int>& nums) {
    int total = 0;
    for (int x : nums) total += x;
    if (total % 2 != 0) return false;
    int target = total / 2;
    vector<bool> reachable(target + 1, false);
    reachable[0] = true;
    for (int x : nums) {
        for (int a = target; a >= x; a--) {
            if (reachable[a - x]) reachable[a] = true;
        }
    }
    return reachable[target];
}

JavaScript

var canPartition = function(nums) {
    const total = nums.reduce(function(a, b) { return a + b; }, 0);
    if (total % 2 !== 0) return false;
    const target = total / 2;
    const dp = new Array(target + 1).fill(false);
    dp[0] = true;
    for (const x of nums) {
        for (let a = target; a >= x; a--) {
            if (dp[a - x]) dp[a] = true;
        }
    }
    return dp[target];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium