mediumDSA

How do you check if an array can be partitioned into two equal-sum subsets?

Q: How do you check if an array can be partitioned into two equal-sum subsets?

**Intuition.** Two equal-sum halves are possible only if the total is even, and then each half must sum to total / 2 . So the question reduces to **subset-sum**: can any subset of the numbers reach total / 2 ? That's a boolean 0/1 knapsack over the target. total 22 → can a subset hit 11? 1 <rect x="110" y="50" width="40" height="34" rx="5" fill="#22c55e" fill-opacity="

109 views

Understand the problem

Explain partition equal subset sum.

dpsubset

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Subset-sum boolean DP

Run Playground

def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for x in nums:
        for s in range(target, x - 1, -1):    # downward = use each x once
            dp[s] = dp[s] or dp[s - x]
    return dp[target]


# --- demo ---
print(can_partition([1, 5, 11, 5]))   # True   ({1,5,5} and {11})
print(can_partition([1, 2, 3, 5]))    # False  (odd total)

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you find the longest palindromic substring?

How does the Sieve of Eratosthenes work?