Algorithm Day90 - Partition Equal Subset Sum

Posted on In , Views:

🧩 Problem Description

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.

Return true if such a partition exists, otherwise return false.

💬 Examples

Example 1

1
2
3
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1,5,5] and [11].

Example 2

1
2
3
Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

💡 Intuition

If the total sum is odd, it’s impossible to split into two equal subsets. Otherwise, the problem reduces to: can we find a subset with sum equal to target = totalSum / 2?

This is the classic subset sum problem and can be solved using dynamic programming (0/1 knapsack style) or using a bitset optimization. We aim for a boolean DP where dp[s] indicates whether a subset with sum s is achievable.

🔢 Java Code (1D DP - optimized 0/1 knapsack)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        if ((sum & 1) == 1) return false;
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int s = target; s >= num; s--) {
                dp[s] = dp[s] || dp[s - num];
            }
            if (dp[target]) return true; // early exit
        }
        return dp[target];
    }
}

Alternative: Bitset (very fast in practice)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int n : nums) sum += n;
        if ((sum & 1) == 1) return false;
        int target = sum / 2;
        BitSet bits = new BitSet(target + 1);
        bits.set(0);
        for (int n : nums) {
            BitSet shifted = bits.get(0, target + 1 - n);
            // Implement left-shift by iterating backwards and setting bits appropriately.
            for (int i = target - n; i >= 0; i--) {
                if (bits.get(i)) bits.set(i + n);
            }
            if (bits.get(target)) return true;
        }
        return bits.get(target);
    }
}

Note: Java’s BitSet doesn’t provide a direct shiftLeft method — you can implement shifting by iterating or using a long-based trick for fixed-size bitsets. The 1D boolean DP is simpler and sufficiently fast for typical constraints.

⏱ Complexity Analysis

  • Time: O(n × target) — where n is the number of elements.
  • Space: O(target) — 1D DP array.

✍️ Summary

  • Check total sum parity first.
  • Reduce to subset-sum with target = totalSum / 2.
  • Use 1D DP (iterate backwards) to avoid reusing elements.
  • Early exit if dp[target] becomes true during iteration.

Related problems: lc-494 (Target Sum), lc-216 (Combination Sum III), lc-698 (Partition to K Equal Sum Subsets).