Partition Equal Subset Sum
The briefingthe full drill, in my own words
The drill: Decide whether an array of positive numbers can be split into two groups with equal totals — every number lands on exactly one side, nothing left out, nothing shared.
An array of positive numbers arrives, and the question is whether it can be divided into two groups whose totals come out exactly equal. Every number has to land in one group or the other — nothing gets left out, and nothing gets shared between the two.
The groups don't need to be the same size, and there's no requirement about which numbers end up where beyond the totals matching. An odd total rules out any split before a single number is even considered.
The answer is a simple yes or no — whether such a balanced split exists at all, not what the split looks like.
- all values are positive
- arrays run up to a couple hundred elements
- individual values stay small enough that half the total is a workable target
- the answer is true/false only, no split needs to be shown
The hintstake only what you need
HINT 1 THE NUDGE
The instant the total is odd, no split can ever balance — rule that out first. Otherwise each side must hit exactly half the sum, so the real question becomes: can some subset reach target = sum ÷ 2?
HINT 2 THE STRUCTURE
Every number faces a binary choice — join the target subset, or don't. That's a decision tree with 2ⁿ leaves, and a lot of those branches chase totals that were already reached another way.
HINT 3 ONE STEP FROM THE ANSWER
Track reachability instead of choices: which totals up to target are buildable using the numbers seen so far? A boolean array updated backward per number turns the search into O(n·target) instead of 2ⁿ.
Coach's boardthe pattern, step by step
Total is 16, so the target is half-sum 8. Sum 0 starts reachable — taking nothing always works.
The splitstwo paces, two languages
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2:
return False
target = total // 2
reachable = [False] * (target + 1)
reachable[0] = True
for x in nums:
for s in range(target, x - 1, -1): # right-to-left: each number used once
if reachable[s - x]:
reachable[s] = True
return reachable[target]class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2:
return False
target = total // 2
n = len(nums)
def backtrack(i: int, remaining: int) -> bool:
if remaining == 0:
return True
if i == n or remaining < 0:
return False
# this number joins the target subset, or it doesn't
return backtrack(i + 1, remaining - nums[i]) or backtrack(i + 1, remaining)
return backtrack(0, target)class Solution {
public 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 s = target; s >= x; s--) {
if (reachable[s - x]) {
reachable[s] = true;
}
}
}
return reachable[target];
}
}class Solution {
public boolean canPartition(int[] nums) {
int total = 0;
for (int x : nums) {
total += x;
}
if (total % 2 != 0) {
return false;
}
return backtrack(nums, 0, total / 2);
}
private boolean backtrack(int[] nums, int i, int remaining) {
if (remaining == 0) {
return true;
}
if (i == nums.length || remaining < 0) {
return false;
}
return backtrack(nums, i + 1, remaining - nums[i]) || backtrack(nums, i + 1, remaining);
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED