Coding interview problems › Dynamic Programming

🪙 Dynamic Programming Medium

Partition Equal Subset Sum

Partition Equal Subset Sum explained: reduce it to subset sum, then solve with a 0/1 knapsack boolean DP. Tested Python, pitfalls and an interactive DP visual.

Also searched as: partition equal subset sum dp · can array be split into two equal sum subsets · subset sum problem

🎒

Try it live Free

0/1 Knapsack (DP)

In the Knapsack lab, watch each row make one take-or-skip decision per item; here each cell only records whether a sum is reachable, but the table fills exactly the same way.

Also useful: Backtracking: Subsets, Permutations & Pruning

Open the playground →

The problem

Given a list of positive integers, decide whether it can be split into two groups with equal sums. Every number must go into exactly one group.

Input[1, 5, 11, 5]
OutputTrue

[1, 5, 5] and [11]

Input[1, 2, 3, 5]
OutputFalse

Total is 11, which is odd.

The key insight

If the total is S, the two groups must each sum to S / 2. So the question becomes: is there a subset that sums to S / 2? That is 0/1 knapsack with yes/no cells: can[t] says whether some subset of the numbers seen so far reaches sum t.

Brute force first: Trying all 2n ways to split the numbers is exponential.

Step-by-step approach

  1. Compute the total. If it is odd, return False immediately.
  2. Set target = total // 2 and a boolean array can of size target + 1 with can[0] = True.
  3. For each number x, loop t from target down to x: can[t] = can[t] or can[t - x].
  4. Stop early if can[target] becomes true.
  5. Return can[target].

Python solution

PYTHON 3tested
def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    can = [True] + [False] * target    # can[t]: some subset sums to t
    for x in nums:
        for t in range(target, x - 1, -1):   # downward: use x once
            if can[t - x]:
                can[t] = True
        if can[target]:
            return True
    return can[target]

Complexity

TimeO(n · S)
SpaceO(S)

Each of n numbers sweeps the boolean table of size S / 2 once, where S is the total sum.

Common mistakes

Frequently asked questions

What is the time and space complexity of Partition Equal Subset Sum?

O(n × S) time and O(S) space, where S is the sum of the array. It is pseudo-polynomial, so very large values make it slow.

How is this problem related to 0/1 knapsack?

It is knapsack where every item's weight and value are the number itself and the capacity is half the total. We only need to know whether the capacity can be filled exactly.

Can I use a bitset to speed it up?

Yes. In Python you can keep reachable sums as bits of one big integer and do bits |= bits << x for each number, then test bit S/2. It is the same DP done many cells at a time.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Dynamic Programming Coin Change (DP) lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.