LeetCode 416 Partition Equal Subset Sum - Four solutions(Med, Java, O(n sum))

0. DP

• Complexity: O(n × sum) time, O(sum) space
• Best for: General case, clean implementation

Core Logic Explained

for (int num : nums) {
    for (int currSum = targetSum; currSum >= num; currSum--) {
        dp[currSum] = dp[currSum] || dp[currSum - num];
    }
}

Why iterate backwards?

• Forward iteration problem: If we go num → targetSum, we might use the same element multiple times
• Example: num = 3, if dp[3] = true, then dp[6] = dp[6] || dp[3] = true
• This incorrectly suggests we can make sum 6 using element 3 twice
• Backward iteration: Updates larger sums first, preventing double usage

DP Transition Meaning:

• dp[currSum]: "Can I make sum currSum without using current num?"
• dp[currSum - num]: "Can I make sum currSum by including current num?"
• ||: "Either way works"

class Solution {
    public boolean canPartition(int[] nums) {
        // TC: O(nsum)
        int totalSum = 0;
        for (int num : nums) totalSum += num;
        if (totalSum % 2 != 0) return false;
        int targetSum = totalSum / 2;
        boolean[] dp = new boolean[targetSum + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int currSum = targetSum; currSum >= num; currSum--) {
                dp[currSum] = dp[currSum] || dp[currSum - num];
                if (dp[targetSum]) return true;
            }
        }
        return dp[targetSum];
    }
}

There are several optimizations and alternative approaches that can improve performance in various scenarios:

1. Bitset Optimization (Fastest for most cases)

• Bitwise operations are extremely fast
• Can process multiple sums simultaneously
• Cache-friendly memory access patterns
• TC: O(n × sum/64)
• MC: O(sum/64)

  Core - Bitset Operations

  for (int num : nums) {
    BitSet shifted = new BitSet(target + 1);
    for (int i = dp.nextSetBit(0); i >= 0 && i + num <= target; i = dp.nextSetBit(i + 1)) {
        shifted.set(i + num);
    }
    dp.or(shifted);
  }
  

  Breaking it down:
• dp.nextSetBit(0): Find first true bit starting from position 0
• shifted.set(i + num): If we can make sum i, we can also make sum i + num
• dp.or(shifted): Merge new possibilities with existing ones
• Why separate BitSet?: Avoid modifying dp while iterating over it

class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) totalSum += num;
        if (totalSum % 2 != 0) return false;

        int target = totalSum / 2;
        BitSet dp = new BitSet(target + 1);
        dp.set(0);

        for (int num : nums) {
            dp.or(dp.get(0, target + 1 - num).stream()
                .mapToObj(i -> i + num)
                .collect(BitSet::new, BitSet::set, BitSet::or));
            if (dp.get(target)) return true;
        }
        return dp.get(target);
    }
}

2. Early Pruning + Sorting (Better average case)

• TC: O(n × sum)
• MC: O(sum)

Core - Sorting Strategy

// Sort in descending order
Arrays.sort(nums);
for (int i = 0; i < nums.length / 2; i++) {
    int temp = nums[i];
    nums[i] = nums[nums.length - 1 - i];
    nums[nums.length - 1 - i] = temp;
}

Why descending order?

• Larger elements first: Higher chance of early termination
• Better pruning: If largest element > target, impossible immediately
• Faster convergence: Reach target sum sooner

Early Termination Logic

if (nums[0] > target) return false;  // Impossible
if (nums[0] == target) return true;  // Found immediately

Impact: Can eliminate entire search space before DP starts

class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) totalSum += num;
        if (totalSum % 2 != 0) return false;

        int target = totalSum / 2;

        // Sort in descending order for better pruning
        Arrays.sort(nums);
        for (int i = 0; i < nums.length / 2; i++) {
            int temp = nums[i];
            nums[i] = nums[nums.length - 1 - i];
            nums[nums.length - 1 - i] = temp;
        }

        // Early termination if largest element > target
        if (nums[0] > target) return false;
        if (nums[0] == target) return true;

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

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

3. Meet-in-the-Middle (Best for large arrays)

• TC: O(2^(n/2))
• MC: O(2^(n/2))

The Split Strategy

Set<Integer> leftSums = getAllSums(nums, 0, n / 2);
Set<Integer> rightSums = getAllSums(nums, n / 2, n);

Why this works:

• Brute force: O(2^n) - check all 2^n subsets
• Split approach: O(2^(n/2) + 2^(n/2)) = O(2^(n/2))
• For n=20: 2^20 = 1M vs 2^10 + 2^10 = 2K operations

Bitmask Generation Explained

for (int mask = 0; mask < (1 << size); mask++) {
    int sum = 0;
    for (int i = 0; i < size; i++) {
        if ((mask & (1 << i)) != 0) {
            sum += nums[start + i];
        }
    }
    sums.add(sum);
}

Bitmask magic:

• mask = 5 (binary: 101) means include elements at positions 0 and 2
• (mask & (1 << i)) checks if bit i is set
• Generates all 2^size possible subset sums

Combination Check

for (int leftSum : leftSums) {
    if (rightSums.contains(target - leftSum)) {
        return true;
    }
}

Logic: If left half sums to x and right half sums to target - x, total = target

class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) totalSum += num;
        if (totalSum % 2 != 0) return false;

        int target = totalSum / 2;
        int n = nums.length;

        // Split array into two halves
        Set<Integer> leftSums = getAllSums(nums, 0, n / 2);
        Set<Integer> rightSums = getAllSums(nums, n / 2, n);

        // Check if any combination equals target
        for (int leftSum : leftSums) {
            if (rightSums.contains(target - leftSum)) {
                return true;
            }
        }
        return false;
    }

    private Set<Integer> getAllSums(int[] nums, int start, int end) {
        Set<Integer> sums = new HashSet<>();
        int size = end - start;

        for (int mask = 0; mask < (1 << size); mask++) {
            int sum = 0;
            for (int i = 0; i < size; i++) {
                if ((mask & (1 << i)) != 0) {
                    sum += nums[start + i];
                }
            }
            sums.add(sum);
        }
        return sums;
    }
}

Time Complexity: O(2^(n/2)) instead of O(n × sum)

4. Optimized DP with Range Pruning

• TC: O(n × reachable)
• MC: O(sum)

The Reachable Concept

int maxReachable = 0;
for (int num : nums) {
    maxReachable = Math.min(maxReachable + num, target);
    for (int sum = maxReachable; sum >= num; sum--) {
        // Only iterate within reachable range
    }
}

Key insight:

• maxReachable: Maximum sum achievable with elements processed so far
• Optimization: Don't check sums beyond what's possible
• Example: If we've only seen [1, 2], no point checking sum = 100

Why This Helps

Without pruning: Always iterate 0 → target
With pruning:    Only iterate 0 → min(accumulated_sum, target)

Impact: Significant speedup when target is much larger than individual elements

class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) totalSum += num;
        if (totalSum % 2 != 0) return false;

        int target = totalSum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        int maxReachable = 0;
        for (int num : nums) {
            maxReachable = Math.min(maxReachable + num, target);

            for (int sum = maxReachable; sum >= num; sum--) {
                dp[sum] = dp[sum] || dp[sum - num];
                if (dp[target]) return true;
            }
        }
        return dp[target];
    }
}

Performance Comparison

Recommendation

For most practical cases, the Bitset approach offers the best performance due to:

• 64x speedup from bitwise operations
• Better cache locality
• Same algorithmic complexity

For competitive programming or when n ≤ 20, Meet-in-the-Middle can be significantly faster.

The original solution remains excellent for its simplicity and guaranteed O(n × sum) performance across all inputs.