The O(n) Club: Partition Equal Subset Sum: Arrays at the Divorce Court

The O(n) Club: Partition Equal Subset Sum—Arrays at the Divorce Court

⚡ TL;DR

Can you separate an array of positive integers into two squads with the same sum? That’s the Partition Equal Subset Sum—classic coding drama. Brute force is for those who enjoy pain. Here’s how Java does it (minus the legal fees):

🧠 How Devs Usually Mess This Up

People see numbers—people sort numbers. It’s a reflex; here, it doesn’t help (the judge doesn’t care who’s taller). Others completely skip the “is total sum odd?” step: sir, that’s your jury nullification moment. And do NOT waste time looking for the actual subsets: the interviewer only wants a yes/no, not your poetry.

🔍 What’s Actually Going On

This is the Knapsack’s laid-back cousin: Subset Sum. Your mission—should you choose not to overthink it—is to find if any subset adds up to half the total. If the sum is odd, just roll your eyes and return false. Otherwise, DP saves you: dp[i] answers “is i-sum bakeable from our ingredients?” Walk the DP array backward—nobody likes a double-dipper at this buffet.

🛠️ PseudoCode

Set target as int target = total / 2;
Check dp[target]—if true, congrats, your array gets joint custody.

For every num, work backwards:

for (int i = target; i >= num; i--)
dp[i] = dp[i] || dp[i - num];

This stops you from using the same number twice.

Form boolean dp array:

boolean[] dp = new boolean[target + 1];
dp[0] = true;

Always can make zero.

Sum the array:

int total = ...;

If odd, answer is a hard no.

💻 The Code

public boolean canPartition(int[] nums) {
    int total = 0;
    for (int x : nums) total += x;
    if (total % 2 != 0) return false; // Odd drama
    int target = total / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    for (int num : nums) {
        for (int i = target; i >= num; i--)
            dp[i] = dp[i] || dp[i - num];
    }
    return dp[target];
}

⚠️ Pitfalls, Traps & Runtime Smacks

The Odd Total: Just say no immediately. Don’t waste cycles for the drama.
Out-of-bounds: Don’t walk off the array. Java will punish you with an Exception and a red stacktrace scar.
Double-counting: Always go backwards to avoid putting the same item on both sides—this isn’t a buffet line.
Massive numbers: Time/space is O(N*sum/2). The interviewer won’t make sum 1,000,000 for a reason. Hopefully.