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

Approach	Time Complexity	Space	Best For
Original DP	O(n × sum)	O(sum)	General case
Bitset	O(n × sum/64)	O(sum/64)	Most practical cases
Early Pruning	O(n × sum)	O(sum)	Arrays with large elements
Meet-in-Middle	O(2^(n/2))	O(2^(n/2))	Small n, large sum
Range Pruning	O(n × reachable)	O(sum)	Sparse solutions

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.

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

0. DP

Core Logic Explained

1. Bitset Optimization (Fastest for most cases)

Core - Bitset Operations

2. Early Pruning + Sorting (Better average case)

Core - Sorting Strategy

Early Termination Logic

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

The Split Strategy

Bitmask Generation Explained

Combination Check

4. Optimized DP with Range Pruning

The Reachable Concept

Why This Helps

Performance Comparison

Recommendation

Comments

More from this blog

LLM for Coding Benchmarks and Datasets

How to change a base model to a reasoning model?

DeepSeek GRPO Explanation (Why we need it? How does it work? What are the findings?)

Beyond Pre-training: The Power of RLHF in LLM Alignment

LeetCode Daily Challenge-3477. Fruits Into Baskets II(Easy, O(n²))

Command Palette

0. DP

Core Logic Explained

1. Bitset Optimization (Fastest for most cases)

Core - Bitset Operations

2. Early Pruning + Sorting (Better average case)

Core - Sorting Strategy

Early Termination Logic

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

The Split Strategy

Bitmask Generation Explained

Combination Check

4. Optimized DP with Range Pruning

The Reachable Concept

Why This Helps

Performance Comparison

Recommendation

Comments

More from this blog