Problem 30.1 · Knapsack DPMedium

Partition Equal Subset Sum

What it teaches: Boolean 0/1 knapsack towards total / 2.

Practise it on judges as “Partition Equal Subset Sum”.

The problem

Return true if the array can be split into two subsets with equal sums.

Example 1

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

[1, 5, 5] and [11].

Constraints

1 ≤ n ≤ 200
1 ≤ nums[i] ≤ 100

Pattern clues in the wording

→ Split into two equal halves

These clues point to Knapsack DP: For each item, decide take or skip under a capacity; dp[c] is the best result using capacity c.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public boolean canPartition(int[] nums) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [1,5,11,5]	true
2	nums = [1,2,3,5]	false

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Boolean knapsack · O(n × sum)2. Bitset · O(n × sum / 64)

Boolean knapsack

Time O(n × sum) Space O(sum)

can[0] = true; for each x, for s from half down to x: can[s] |= can[s − x].

Approach 1

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2 == 1) return false;
        int half = total / 2;
        boolean[] can = new boolean[half + 1];
        can[0] = true;
        for (int x : nums)
            for (int s = half; s >= x; s--) can[s] |= can[s - x];
        return can[half];
    }
}

Verdict: sum ≤ 20 000 keeps it small.

Bitset

Time O(n × sum / 64) Space O(sum / 64)

Bit s of a BitSet means "sum s reachable". For each x: bits |= bits << x.

Approach 2

import java.math.BigInteger;

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2 == 1) return false;
        BigInteger bits = BigInteger.ONE;
        for (int x : nums) bits = bits.or(bits.shiftLeft(x));
        return bits.testBit(total / 2);
    }
}

Verdict: Word-level parallelism; a nice trick for larger sums.

Before you submit

Edge cases and common mistakes

Test these inputs

Odd total
Single element
One element larger than half

Mistakes people make

Looping s upwards (reuses an element).

Interview

Follow-up questions

What about splitting into k equal subsets?

Command Palette