Partition equal subset sum

Problem Link: LeetCode 416. Partition Equal Subset Sum

Problem Statement:
Given a non-empty array nums containing only positive integers, determine if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Solution Flow

1. Recursion (Pick-Not Pick Approach)

Intuition:

If total sum is odd → impossible to partition → return false
If even, find subset with sum = total_sum / 2 (classic subset sum problem)
For each element: include or exclude in subset

Java Code:

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums) total += num;
        if (total % 2 != 0) return false;
        int target = total / 2;
        return subsetSum(nums, nums.length, target);
    }

    private boolean subsetSum(int[] nums, int n, int target) {
        if (target == 0) return true;
        if (n == 0) return false;

        if (nums[n - 1] > target)
            return subsetSum(nums, n - 1, target);
        return subsetSum(nums, n - 1, target) ||
               subsetSum(nums, n - 1, target - nums[n - 1]);
    }
}

Complexity:

Time: O(2^n)
Space: O(n) (recursion stack)

2. Memoization (Top-Down DP)

Intuition:
Cache results using a 2D dp[n][target] table.

Java Code:

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums) total += num;
        if (total % 2 != 0) return false;
        int target = total / 2;
        Boolean[][] dp = new Boolean[nums.length + 1][target + 1];
        return subsetSum(nums, nums.length, target, dp);
    }

    private boolean subsetSum(int[] nums, int n, int target, Boolean[][] dp) {
        if (target == 0) return true;
        if (n == 0) return false;
        if (dp[n][target] != null) return dp[n][target];

        if (nums[n - 1] > target)
            dp[n][target] = subsetSum(nums, n - 1, target, dp);
        else
            dp[n][target] = subsetSum(nums, n - 1, target, dp) ||
                            subsetSum(nums, n - 1, target - nums[n - 1], dp);
        return dp[n][target];
    }
}

Complexity:

Time: O(n * target)
Space: O(n * target) (DP table + recursion stack)

3. Tabulation (Bottom-Up DP)

Intuition:
Build a DP table from base cases up.

Java Code:

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums) total += num;
        if (total % 2 != 0) return false;
        int target = total / 2, n = nums.length;
        boolean[][] dp = new boolean[n + 1][target + 1];

        for (int i = 0; i <= n; i++) dp[i][0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                if (nums[i - 1] > j)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
        return dp[n][target];
    }
}

Dry Run (nums = [1, 5, 11, 5], target = 11):

    j →  0  1  2  3  4  5  6  7  8  9 10 11
i=0:  T  F  F  F  F  F  F  F  F  F  F  F
i=1:  T  T  F  F  F  F  F  F  F  F  F  F
i=2:  T  T  F  F  F  T  T  F  F  F  F  F
i=3:  T  T  F  F  F  T  T  F  F  F  F  T
i=4:  T  T  F  F  F  T  T  F  F  F  T  T

Result: dp[4][11] = true

4. Space Optimization

Intuition:
Use a 1D array; reverse iterate to prevent premature overwrites.

Java Code:

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums) total += num;
        if (total % 2 != 0) return false;
        int target = total / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }
}

Dry Run:

nums = [1, 5, 11, 5], target = 11

Step 1: num = 1 → dp[1] = true
→ dp = [T, T, F, F, F, F, F, F, F, F, F, F]

Step 2: num = 5 → dp[5] = T, dp[6] = T
→ dp = [T, T, F, F, F, T, T, F, F, F, F, F]

Step 3: num = 11 → dp[11] = T (since dp[0] = T)
→ dp = [T, T, F, F, F, T, T, F, F, F, F, T]

Step 4: num = 5 → dp[10] = T, dp[11] remains T
→ Final: dp[11] = T

Complexity:

Time: O(n * target)
Space: O(target)

Comparison Table

Approach	Time Complexity	Space Complexity	Notes
Recursion	`O(2^n)`	`O(n)`	Simple but exponential
Memoization (Top-Down)	`O(n * target)`	`O(n * target)`	Caches results, avoids recomputation
Tabulation (Bottom-Up)	`O(n * target)`	`O(n * target)`	Iterative, avoids recursion stack
Space Optimized	`O(n * target)`	`O(target)`	Efficient with reverse iteration trick

Key Insights

Problem Reduction:
Partition problem → Subset Sum with target = total_sum / 2
Space Optimization:
Reverse iteration allows in-place updates without overwriting dependencies.
Edge Cases:
- If total_sum is odd, immediately return false
- If target == 0, always return true
- If only one number exists, check if num == target