Partition Equal Subset Sum

Q: Why is Partition Equal Subset Sum a 0/1 knapsack problem?

You have a knapsack of size target = total / 2 and must fill it exactly, using each value at most once. Taking a value or leaving it is the 0/1 choice, and the size of a value is the value itself. The knapsack table of reachable sums answers it in O(n × target) time.

Q: What is the time complexity of Partition Equal Subset Sum?

The table approach takes O(n × target) time, where target is half the total, and O(target) memory with one row. With 200 values of at most 100 that is about 2 × 10^6 steps. The bound grows with the size of the values, not only their count, so it is called pseudo-polynomial: with values near 10^9 no table would fit, and the general problem is NP-complete.

Q: Why does the inner loop go from the target down to the value?

Walking down means reach[s-num] is read before this value can change it, so it still describes the values before num . Walking up would let a sum built with num be extended by num again, which counts one value many times. The upward loop is the right one for unlimited copies, as in Coin Change, and the wrong one here.

MediumDynamic programming

+10

You get an array nums of positive integers. Decide whether you can split the values into two groups whose sums are equal. Every value goes into exactly one group, and a group can take values from any positions. Return true if such a split exists and false otherwise.

Function

canPartition(nums: integer-array) → boolean

numsinteger-array: the positive values to split into two groups
Returnsboolean: true when the values can form two groups with equal sums, false otherwise

Constraints

1 ≤ nums.length ≤ 200
1 ≤ nums[i] ≤ 100

Examples

Input: nums = [6, 1, 4, 9, 2]
Output: true
Explanation: The total is 22, so each group needs 11. The groups 9 + 2 and 6 + 1 + 4 both make 11, so the answer is true.

Input: nums = [4, 7, 2, 9, 6]
Output: false
Explanation: The total is 28, so each group needs 14. The group that holds 9 needs 5 more, and no mix of 4, 7, 2 and 6 makes 5, so the answer is false even though the total is even.

Input: nums = [1, 2, 3, 5]
Output: false
Explanation: The total is 11. Two equal whole numbers always add up to an even number, so an odd total can never be split and the answer is false.

+18 hidden tests on Submit

Follow-up

When no equal split exists, can you return the smallest possible difference between the two group sums?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Each group must hold exactly half of the total, so the real question is whether some subset of nums adds up to target = total / 2. Trying every subset costs 2^n, which is hopeless for 200 values. The sums themselves are small, though: target is at most 200 × 100 / 2 = 10^4. Recording which sums are reachable, one value at a time, turns the search into a 0/1 knapsack table that fills in O(n × sum) steps.

Try every subset with recursion

Correct, but does not finish on the largest tests

Intuition

Start with the total. If it is odd, no split exists, because two equal whole numbers add up to an even number. Otherwise each group must make exactly target = total / 2. Once you find values that make target, the values you did not pick make the other half on their own. So one question is enough: does some subset reach target?

Walk the values in order and make one choice for each: put it in the first group, or leave it for the second. A helper reach(i, remaining) answers whether the values from index i on can make up remaining. It returns true when remaining hits 0, false when it runs out of values or drops below 0, and otherwise tries both choices for nums[i].

Every subset is one path of choices, so the search cannot miss a split, and the answer is correct. It is slow because there are 2^n paths, and an input with no split forces it to try almost all of them. Take 199 copies of 100 and one 98: the total is 19998, the target 9999 is never hit, and the search tries every way to pick at most 99 of the hundreds, about 4 × 10^59 paths. Even 40 values give 2^40, about 10^12 paths.

Algorithm

Add up nums. If the total is odd, return false.
Set target to half the total.
Write reach(i, remaining): return true when remaining is 0, and false when i is past the last value or remaining is below 0.
Otherwise return reach(i+1, remaining-nums[i]) or reach(i+1, remaining): take the value or leave it.
Return reach(0, target).

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False

    # Can some of the values from index i on add up to exactly remaining?
    def reach(i, remaining):
        if remaining == 0:
            return True
        if i == len(nums) or remaining < 0:
            return False
        # Put nums[i] in the first group, or leave it for the second one
        return reach(i + 1, remaining - nums[i]) or reach(i + 1, remaining)

    return reach(0, total // 2)

Fill a table by value and sum

Intuition

The recursion asks the same question over and over. reach(i, remaining) depends on two numbers only: i from 0 to n and remaining from 0 to target. That makes at most (n+1) × (target+1) different questions, about 201 × 10001 ≈ 2 × 10^6 at the limits, few enough to answer every one of them once.

Build the answers forward in a table. can[i][s] says whether some of the first i values add up to s. With no values, only the sum 0 is possible, so row 0 is false except can[0][0]. The value num = nums[i-1] gives two ways to reach s: leave num out, so the earlier values already reach s, or put it in, so the earlier values reach s-num. That is the whole rule: can[i][s] = can[i-1][s] or can[i-1][s-num], where the second part only counts when s ≥ num. Each row reads only the row above, so every value is used at most once.

On [6, 1, 4, 9, 2] with target 11, the reachable sums grow from {0} to {0, 6}, then {0, 1, 6, 7}, then {0, 1, 4, 5, 6, 7, 10, 11}. Sum 11 appears after the 4 (6 + 1 + 4), and later rows keep it. The answer is can[n][target]. Every cell costs constant work, so time and memory are both O(n × target).

Algorithm

Return false for an odd total and set target to half of it.
Make a table with n+1 rows and target+1 columns, all false, and set can[0][0] to true.
For each row i from 1 to n, take num = nums[i-1].
For each sum s from 0 to target, set can[i][s] to can[i-1][s] or, when s ≥ num, can[i-1][s-num].
Return can[n][target].

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False
    target = total // 2
    n = len(nums)

    # can[i][s] is True when some of the first i values add up to s
    can = [[False] * (target + 1) for _ in range(n + 1)]
    can[0][0] = True
    for i in range(1, n + 1):
        num = nums[i - 1]
        for s in range(target + 1):
            # Leave num out, or put it in and reach s - num with the values before it
            can[i][s] = can[i - 1][s] or (s >= num and can[i - 1][s - num])
    return can[n][target]

One row of sums, filled from the top down

Intuition

Each row of the table reads only the row above it, so one row is enough if you update it in place: reach[s] says whether some of the values seen so far add up to s. The danger is the order of the updates. If you walk s upward, reach[s-num] may already have been switched on by the same num. With [3, 9] and target 6, the 3 marks reach[3], then reads it to mark reach[6], as if you owned two 3s, and you answer true for a split that does not exist.

Walk s downward, from target to num. Then s-num is a smaller index that this value has not touched yet, so reach[s-num] still holds the answer from before num arrived. That is exactly can[i-1][s-num] from the table, and the single row does the work of the whole table.

You can also stop the moment reach[target] turns true, because later values only add reachable sums and never remove one. The worst case is still O(n × target) steps, about 2 × 10^6, and the memory drops to target + 1 booleans.

Algorithm

Return false for an odd total and set target to half of it.
Make reach with target + 1 entries, all false except reach[0].
For each value num, walk s from target down to num and set reach[s] to true when reach[s-num] is true.
After each value, return true if reach[target] is true.
If the loop ends, return reach[target], which is false.

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

    # reach[s] is True when some of the values seen so far add up to s
    reach = [False] * (target + 1)
    reach[0] = True
    for num in nums:
        # Walk the sums downward so num is used at most once
        for s in range(target, num - 1, -1):
            if reach[s - num]:
                reach[s] = True
        if reach[target]:
            return True
    return reach[target]

Pitfalls and edge cases

Wrong answers here come from trusting a greedy rule, from skipping the odd check, and from reusing a value in the one-row table.

Walking the sums upward in the one-row version uses a value more than once. With [3, 9] the target is 6, the 3 marks sum 3 and then sum 6, and you answer true.
Skipping the odd check: for [1, 2] the total 3 rounds down to a target of 1, the value 1 reaches it, and you answer true for a split that cannot exist.
Greedy filling, such as sorting and always adding to the lighter group, fails on [3, 3, 2, 2, 2]: it ends at 7 against 5, while 3 + 3 = 2 + 2 + 2.
A value larger than the target, as in [2, 2, 2, 10]. A downward loop from target to num then runs zero times, which is right, but a range such as (num+1):(target+1) in R counts backward and breaks the table. Skip such values.
An even total is not enough: [4, 7, 2, 9, 6] sums to 28 and still has no split.
In Lua and R arrays start at 1, so the entry for sum s sits at index s + 1.

Frequently asked questions4

Why is Partition Equal Subset Sum a 0/1 knapsack problem?

You have a knapsack of size target = total / 2 and must fill it exactly, using each value at most once. Taking a value or leaving it is the 0/1 choice, and the size of a value is the value itself. The knapsack table of reachable sums answers it in O(n × target) time.

What is the time complexity of Partition Equal Subset Sum?

The table approach takes O(n × target) time, where target is half the total, and O(target) memory with one row. With 200 values of at most 100 that is about 2 × 10^6 steps. The bound grows with the size of the values, not only their count, so it is called pseudo-polynomial: with values near 10^9 no table would fit, and the general problem is NP-complete.

Why does the inner loop go from the target down to the value?

Walking down means reach[s-num] is read before this value can change it, so it still describes the values before num. Walking up would let a sum built with num be extended by num again, which counts one value many times. The upward loop is the right one for unlimited copies, as in Coin Change, and the wrong one here.

Can Partition Equal Subset Sum be solved with a bitset?

Yes. Store the reachable sums as the bits of one large number, starting with only bit 0 set. For each value, bits |= bits << num adds that value to every reachable sum at once, and the answer is whether bit target is set. It is the same table, but each machine word handles 64 sums at a time, so it runs much faster in practice.

Python

def canPartition(nums):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

nums = [6, 1, 4, 9, 2]

Expected

true

Partition Equal Subset Sum

Function

Constraints

Examples

Hints

Solution

Try every subset with recursion

Fill a table by value and sum

One row of sums, filled from the top down

Pitfalls and edge cases

Frequently asked questions4

Similar problems