Partition Equal Subset Sum

Intuition

Can we select a subset summing to totalSum/2? Classic 0/1 knapsack boolean DP. If totalSum is odd, return false immediately. dp[j] = true if subset summing to j is achievable.

Algorithm

1If sum%2==1: return false. target=sum/2.
2dp[0]=true, dp[1..target]=false.
3For each num: for j from target down to num: dp[j] |= dp[j-num].
4Return dp[target].

Example Walkthrough

Input: arr=[1,5,11,5], sum=22

1.target=11. After processing: dp[11]=true via [1,5,5] or [11]. Return true.

Output: true

Common Pitfalls

•Process in reverse to avoid using the same element twice (0/1 constraint).

Partition Equal Subset Sum.java

Java

// Approach: DP (0/1 Knapsack). Find if any subset sums to totalSum/2. dp[j] = can we achieve sum j.
// Time: O(n * sum) Space: O(sum)
class Solution {
    static boolean equalPartition(int arr[]) {
        int sum = 0;
        for (int a : arr)
            sum += a;
        if (sum % 2 != 0)
            return false;
        int target = sum / 2;
        Boolean dp[][] = new Boolean[arr.length][target + 1];
        return f(arr.length - 1, target, arr, dp);

    }

    static boolean f(int ind, int tar, int arr[], Boolean dp[][]) {
        if (ind < 0)
            return false;
        if (tar == 0)
            return true;

        if (dp[ind][tar] != null)
            return dp[ind][tar];

        boolean nt = f(ind - 1, tar, arr, dp);
        boolean t = false;
        if (tar - arr[ind] >= 0)
            t = f(ind - 1, tar - arr[ind], arr, dp);
        return dp[ind][tar] = nt || t;
    }
}

Was this solution helpful?