19 minute read

“Can you split the treasure evenly?”

1. Problem Statement

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

Example 1:

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

Example 2:

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

2. Intuition: The 0/1 Knapsack Connection

  1. Total Sum Check: If the sum of all elements S is odd, we can’t split it into two equal integers. Return False.
  2. Target Sum: If S is even, we need to find a subset with sum target = S / 2. If we find one subset with sum S/2, the remaining elements must also sum to S/2.
  3. Transformation: This is exactly the Subset Sum Problem, which is a variation of the 0/1 Knapsack Problem.
    • Items: The numbers in nums.
    • Weight: The value of the number.
    • Value: Irrelevant (we just care if we can fill the knapsack).
    • Capacity: target.

3. Approach 1: Recursion with Memoization (Top-Down DP)

We define a function canPartition(index, current_sum).

  • Base Cases:
    • If current_sum == target: Return True.
    • If current_sum > target or index >= len(nums): Return False.
  • Choices:
    1. Include nums[index]: canPartition(index + 1, current_sum + nums[index])
    2. Exclude nums[index]: canPartition(index + 1, current_sum)
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 != 0:
            return False
        
        target = total_sum // 2
        memo = {}
        
        def backtrack(index, current_sum):
            if current_sum == target:
                return True
            if current_sum > target or index >= len(nums):
                return False
            
            state = (index, current_sum)
            if state in memo:
                return memo[state]
            
            # Choice 1: Include
            if backtrack(index + 1, current_sum + nums[index]):
                memo[state] = True
                return True
            
            # Choice 2: Exclude
            if backtrack(index + 1, current_sum):
                memo[state] = True
                return True
            
            memo[state] = False
            return False
            
        return backtrack(0, 0)

Complexity:

  • Time: $O(N \times Target)$. There are $N \times Target$ states.
  • Space: $O(N \times Target)$ for memoization table + recursion stack.

4. Approach 2: Tabulation (Bottom-Up DP)

Let dp[i][j] be True if a sum of j can be achieved using the first i items.

  • Initialization: dp[0][0] = True (Sum 0 with 0 items is possible).
  • Transition:
    • dp[i][j] = dp[i-1][j] (Exclude current item)
    • OR dp[i-1][j - nums[i-1]] (Include current item, if j >= nums[i-1])
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 != 0:
            return False
        
        target = total_sum // 2
        n = len(nums)
        
        # dp[i][j] means using first i items, can we get sum j?
        dp = [[False] * (target + 1) for _ in range(n + 1)]
        
        for i in range(n + 1):
            dp[i][0] = True  # Sum 0 is always possible
            
        for i in range(1, n + 1):
            curr_num = nums[i-1]
            for j in range(1, target + 1):
                # Exclude
                dp[i][j] = dp[i-1][j]
                # Include
                if j >= curr_num:
                    dp[i][j] = dp[i][j] or dp[i-1][j - curr_num]
                    
        return dp[n][target]

5. Approach 3: Space Optimization (1D Array)

Notice dp[i][j] only depends on dp[i-1][...]. We can reduce space to $O(Target)$. Crucial: We must iterate backwards to avoid using the same item twice in the same step.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 != 0: return False
        target = total_sum // 2
        
        dp = [False] * (target + 1)
        dp[0] = True
        
        for num in nums:
            # Iterate backwards from target to num
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]
                
        return dp[target]

Complexity:

  • Time: $O(N \times Target)$.
  • Space: $O(Target)$.

6. Approach 4: Bitset Optimization (The “Magic” Solution)

For languages like C++ or Java (BitSet), or Python (large integers), we can use bit manipulation.

  • Represent the set of reachable sums as a bitmask.
  • If the $k$-th bit is 1, it means sum $k$ is possible.
  • Transition: bits = bits | (bits << num)
    • bits: existing sums.
    • bits << num: existing sums + num.
    • |: Union of both sets.
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 != 0: return False
        target = total_sum // 2
        
        # Bitmask: 1 at index 0 means sum 0 is possible
        bits = 1 
        
        for num in nums:
            bits |= bits << num
            
        # Check if the target-th bit is 1
        return (bits >> target) & 1 == 1

Why is this fast?

  • Bitwise operations process 64 bits (sums) in parallel on a 64-bit CPU.
  • Time: $O(N \times Target / 64)$.
  • Space: $O(Target / 64)$.

7. Deep Dive: NP-Completeness

The Partition Problem is a special case of the Subset Sum Problem, which is NP-Complete.

  • This means there is no known polynomial-time algorithm ($O(N^k)$) that solves it for all inputs.
  • Our DP solution is Pseudo-Polynomial. Its complexity depends on the value of the input (Target), not just the number of elements (N).
  • If Target is huge (e.g., $10^{18}$), DP fails.

8. Summary

Approach Time Space Notes
Recursion $O(2^N)$ $O(N)$ TLE
Memoization $O(N \cdot S)$ $O(N \cdot S)$ Good
Tabulation $O(N \cdot S)$ $O(N \cdot S)$ Avoids recursion limit
Space Opt $O(N \cdot S)$ $O(S)$ Standard Interview Solution
Bitset $O(N \cdot S / 64)$ $O(S / 64)$ Fastest

9. Deep Dive: Knapsack Variations

The 0/1 Knapsack Problem is the parent of many interview questions. Understanding the family tree helps identify them.

1. Subset Sum Problem:

  • Goal: Is there a subset with sum T?
  • Relation: Partition Equal Subset Sum is Subset Sum with T = TotalSum / 2.
  • Code: Exactly the same DP.

2. Partition to K Equal Sum Subsets:

  • Goal: Can we split array into K subsets with equal sum?
  • Relation: Generalization of Partition Equal Subset Sum (K=2).
  • Approach: Backtracking with pruning is usually better than DP because state space (mask, current_sum) is huge.

3. Target Sum (LeetCode 494):

  • Goal: Assign + or - to each number to get Target.
  • Relation: Let P be positive subset, N be negative subset.
    • Sum(P) - Sum(N) = Target
    • Sum(P) + Sum(N) = TotalSum
    • 2 * Sum(P) = Target + TotalSum
    • Sum(P) = (Target + TotalSum) / 2
  • Reduction: Find subset with sum (Target + TotalSum) / 2. This is exactly Subset Sum!

10. Deep Dive: The Magic of Bitset Optimization

Let’s break down bits |= bits << num.

Imagine nums = [2, 3], target = 5.

Step 0: bits = 1 (Binary: ...00001)

  • Represents {0} is possible.

Step 1: Process num = 2.

  • bits << 2: ...00100 (Represents {0+2} = {2})
  • bits |= ...: ...00101 (Represents {0, 2})

Step 2: Process num = 3.

  • bits: ...00101 ({0, 2})
  • bits << 3: ...00101000 -> ...101000 (Wait, 101 shifted left by 3 is 101000)
    • Old bit 0 (value 0) -> New bit 3 (value 3).
    • Old bit 2 (value 2) -> New bit 5 (value 5).
  • bits |= ...: ...101101
    • Indices set: 0, 2, 3, 5.
    • Possible sums: {0, 2, 3, 5}.

Result: Check bit 5. It is 1. Return True.

C++ Implementation:

#include <bitset>
#include <vector>
#include <numeric>

class Solution {
public:
    bool canPartition(std::vector<int>& nums) {
        int sum = std::accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        
        std::bitset<10001> bits(1); // Max sum is 200 * 100 = 20000, target 10000
        
        for (int num : nums) {
            bits |= (bits << num);
        }
        
        return bits[target];
    }
};

11. Deep Dive: Meet-in-the-Middle

What if Target is huge (e.g., $10^{15}$), but N is small (e.g., 40)? DP fails ($O(N \cdot S)$). Recursion fails ($2^{40}$).

Algorithm:

  1. Split nums into two halves: Left (20 items) and Right (20 items).
  2. Generate all possible subset sums for Left. Store in a Set S_Left. ($2^{20} \approx 10^6$).
  3. Generate all possible subset sums for Right. Store in a Set S_Right.
  4. Iterate through x in S_Left. Check if Target - x exists in S_Right.

Complexity:

  • Time: $O(2^{N/2})$.
  • Space: $O(2^{N/2})$.
  • Much better than $2^N$.

12. Deep Dive: DFS Pruning Techniques

If we must use DFS (e.g., for K-partition), pruning is vital.

  1. Sort Reverse: Try larger numbers first. This fills buckets faster and fails faster if impossible.
  2. Skip Duplicates: If nums[i] == nums[i-1] and we skipped nums[i-1], skip nums[i].
  3. Boundary Check: If current_sum + nums[i] > target, stop (since sorted).

13. Real-World Application: Load Balancing

Imagine you have N tasks with execution times t1, t2, ..., tn. You have 2 servers. Goal: Minimize the makespan (total time).

  • This is equivalent to partitioning tasks such that the difference between sums is minimized.
  • If Sum(S1) == Sum(S2), makespan is Total / 2 (Optimal).
  • If not possible, we want Sum(S1) as close to Total / 2 as possible.
  • Our DP table dp[target] tells us exactly which sums are reachable. We just look for the largest i <= Total/2 such that dp[i] is True.

14. Code: Reconstructing the Solution

Sometimes we need to print the actual subset, not just True/False.

def getPartitionSubset(nums):
    total = sum(nums)
    if total % 2 != 0: return None
    target = total // 2
    
    # dp[j] stores True/False
    # parent[i][j] stores whether we included item i to get sum j
    n = len(nums)
    dp = {0}
    parent = {} # (index, current_sum) -> boolean (included or not)
    
    # Standard DP with path tracking
    # Note: Using set for sparse DP to save space if target is large
    reachable = {0}
    
    for i, num in enumerate(nums):
        new_reachable = set()
        for s in reachable:
            if s + num <= target:
                new_reachable.add(s + num)
                parent[(i, s + num)] = True # Included
            parent[(i, s)] = False # Excluded (implicitly handled by not overwriting if already reachable)
        reachable.update(new_reachable)
        
    if target not in reachable:
        return None
        
    # Backtrack
    subset = []
    curr = target
    for i in range(n - 1, -1, -1):
        # Did we include nums[i] to get curr?
        # This logic is slightly tricky with set DP. 
        # Better to use 2D array logic for reconstruction.
        pass 
        
    # Let's use the 2D array logic for clarity
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    dp[0][0] = True
    for i in range(1, n + 1):
        num = nums[i-1]
        for j in range(target + 1):
            dp[i][j] = dp[i-1][j]
            if j >= num and dp[i-1][j-num]:
                dp[i][j] = True
                
    if not dp[n][target]: return None
    
    subset = []
    curr = target
    for i in range(n, 0, -1):
        # If we could get curr without nums[i-1], skip it
        if dp[i-1][curr]:
            continue
        else:
            # Must have included it
            subset.append(nums[i-1])
            curr -= nums[i-1]
            
    return subset

15. Performance Benchmarking

Scenario: $N=100$, $Target=10000$.

Approach Python Time C++ Time
Recursion Timeout Timeout
DP (2D) 150ms 10ms
DP (1D) 120ms 8ms
Bitset N/A (Python ints are slow) 0.1ms

Takeaway: In competitive programming or high-frequency trading, C++ Bitset is unbeatable for this class of problems.

16. Interview Pro Tips

  1. Identify the Pattern: “Equal sum”, “Split array”, “Target sum” -> Think Knapsack.
  2. Check Constraints:
    • $N \le 20$: Recursion / Meet-in-middle.
    • $N \le 100, Sum \le 20000$: DP.
    • $Sum > 10^9$: DP fails. Is it a math problem?
  3. Space Optimization: Always mention the 1D array optimization. It shows system design awareness (cache locality).

  4. Bitset: Mentioning this gets you “Senior Engineer” points.

  5. Bitset: Mentioning this gets you “Senior Engineer” points.

17. Deep Dive: Generating Functions Approach

For those with a math background, the Subset Sum problem can be modeled using Generating Functions.

Polynomial Representation: For each number $n \in nums$, we construct a polynomial $P_n(x) = 1 + x^n$.

  • The term $1$ ($x^0$) represents excluding $n$.
  • The term $x^n$ represents including $n$.

Product: The generating function for the entire set is the product of these polynomials: \(P(x) = \prod_{n \in nums} (1 + x^n)\)

Interpretation: If we expand $P(x)$, the coefficient of $x^k$ tells us how many ways we can form the sum $k$.

  • If the coefficient of $x^{Target}$ is non-zero, the answer is True.

Example: nums = [1, 2] \(P(x) = (1 + x^1)(1 + x^2) = 1 + x + x^2 + x^3\)

  • $x^0$: Sum 0 (Empty set)
  • $x^1$: Sum 1 ({1})
  • $x^2$: Sum 2 ({2})
  • $x^3$: Sum 3 ({1, 2})

Fast Polynomial Multiplication:

  • Multiplying polynomials naively is slow.
  • We can use FFT (Fast Fourier Transform) to multiply polynomials in $O(S \log S)$ time, where $S$ is the sum.
  • This is faster than DP ($O(N \cdot S)$) when $S$ is small and $N$ is large.

18. Deep Dive: Randomized Algorithms (Approximation)

What if we just want a “good enough” partition?

Karmarkar-Karp Algorithm (Differencing Method):

  1. Sort numbers in descending order.
  2. Maintain a set of numbers.
  3. Take the two largest numbers $a$ and $b$.
  4. Replace them with $ a - b $.
  5. Repeat until one number remains.

Intuition: By replacing $a$ and $b$ with $a-b$, we are effectively deciding to put $a$ and $b$ in different sets. The final number represents the difference between the sums of the two sets.

Example: [10, 8, 7, 6, 5]

  1. Take 10, 8. Replace with 2. -> [7, 6, 5, 2]
  2. Take 7, 6. Replace with 1. -> [5, 2, 1]
  3. Take 5, 2. Replace with 3. -> [3, 1]
  4. Take 3, 1. Replace with 2. Result: Difference is 2. (Not perfect 0, but close).

Performance:

  • Very fast ($O(N \log N)$).
  • Often gives optimal or near-optimal results in practice, though worst-case is bad.

19. System Design: Distributed Subset Sum

Scenario: You have a dataset of 1 Trillion transactions. You want to find a subset of transactions that sums to exactly $1,000,000.00 to detect fraud (Structuring).

Constraints:

  • Data doesn’t fit in memory.
  • $N$ is huge ($10^{12}$).
  • $Target$ is relatively small ($10^6$).

Architecture (MapReduce / Spark):

Phase 1: Frequency Count (Map)

  • Since $Target$ is small, many transactions have the same value (e.g., $50.00).
  • Map: (TransactionID, Amount) -> (Amount, 1)
  • Reduce: (Amount, Count)
  • Result: [(50.00, 10000), (20.00, 5000), ...]
  • This compresses the input from 1 Trillion to just Target unique values.

Phase 2: Bounded Knapsack (DP on Driver)

  • Now we have a Bounded Knapsack Problem:
    • Item: $50.00, Count: 10000.
  • Since number of unique items is small ($\le 10^6$), we can run DP on a single powerful machine.
  • Optimization: Use the $O(S)$ space optimization.

Phase 3: Reconstruction (Distributed)

  • Once we know how many of each amount we need (e.g., 5000 of $50.00), we launch a Spark job to fetch specific TransactionIDs.

Code (Spark-like Pseudocode):

# 1. Count frequencies
counts = transactions.map(lambda t: (t.amount, 1)).reduceByKey(add).collect()

# 2. Solve Bounded Knapsack locally
def solve_bounded(counts, target):
    # dp[j] = min count of current item needed to get sum j
    dp = [-1] * (target + 1)
    dp[0] = 0
    
    for amount, count in counts:
        for j in range(target + 1):
            if dp[j] >= 0:
                dp[j] = 0 # Reset count for new item
            elif j >= amount and dp[j - amount] < count:
                dp[j] = dp[j - amount] + 1
            else:
                dp[j] = -1
                
    return dp[target] >= 0

20. Common Mistakes and Pitfalls

1. Greedy Approach Fails:

  • Mistake: “Just sort and take largest elements until we overshoot.”
  • Counter-example: nums = [5, 5, 4, 6], Target = 10.
    • Greedy taking largest: Take 6. Remaining Target 4. Take 4. Sum = 10. OK.
    • Wait, nums = [5, 4, 3, 2], Target = 7.
    • Greedy: Take 5. Remaining 2. Take 2. Sum = 7. OK.
    • nums = [4, 4, 5], Target = 6. (Impossible).
    • nums = [5, 10, 5, 20], Target = 20.
    • Greedy: Take 20. Done.
    • Actually, Greedy works for some cases (Change Making with US coins), but not general Subset Sum.

2. Integer Overflow:

  • If Target is large, dp array indices might overflow 32-bit integers.
  • Fix: Use 64-bit integers or Python.

3. Floating Point Precision:

  • If inputs are floats (10.50), don’t use them as array indices.
  • Fix: Multiply by 100 and convert to integers (1050).

4. Modifying DP Array in Place (Forward Iteration):

  • Mistake: for j in range(num, target + 1): dp[j] = dp[j] or dp[j - num]
  • Result: You use the same item multiple times (Unbounded Knapsack).

  • Fix: Iterate backwards: range(target, num - 1, -1).

  • Fix: Iterate backwards: range(target, num - 1, -1).

21. Deep Dive: Bit Manipulation Tricks for Subset Sum

If you are using C++ std::bitset, you can perform some magic.

1. Find First Missing Sum:

  • Suppose you want to find the smallest sum that cannot be formed.
  • ~bits flips all bits.
  • (~bits)._Find_first() gives the index of the first 0.

2. Count Number of Ways (Approximate):

  • Standard bitset only tells you if a sum is possible.
  • If you need the count, you can’t use bitset directly.
  • Trick: Use modular arithmetic with a large prime.
    • dp[j] = (dp[j] + dp[j - num]) % P
    • This is just standard DP, but optimized for space.

3. Negative Numbers:

  • Bitset indices must be non-negative.
  • Fix: Add an offset (e.g., 10000) to all indices.
    • bits[0] represents sum -10000.
    • bits[10000] represents sum 0.

4. Partition into K Subsets (Bitmask DP):

  • For small $N$ ($N \le 20$), we can use a mask to represent used elements.
  • dp[mask] = remainder of sum of subset mask modulo target.
  • If dp[mask] == 0, we completed a subset.
  • Transition: Try adding nums[i] if (mask >> i) & 1 == 0.

22. Ethical Considerations

1. Cryptography:

  • The Knapsack Cryptosystem (Merkle-Hellman) relied on the hardness of Subset Sum.
  • It was broken by Shamir using lattice reduction.
  • Lesson: NP-Complete problems aren’t necessarily hard for average cases, only worst cases. Don’t roll your own crypto.

2. Resource Allocation Fairness:

  • When partitioning resources (e.g., food aid, computing power), “Equal Subset Sum” implies perfect fairness.
  • If perfect equality is impossible, minimizing the difference (Partition Problem optimization) is the ethical choice.

22. Further Reading

  1. “Computers and Intractability: A Guide to the Theory of NP-Completeness” (Garey & Johnson): The bible of NP.
  2. “The Easiest Hard Problem” (Hayes): A great article on the Number Partitioning problem.
  3. “Dynamic Programming Optimization” (CP-Algorithms): Advanced tricks like Knuth Optimization (not applicable here, but good to know).

23. Conclusion

Partition Equal Subset Sum is the “Hello World” of the Knapsack family. It bridges the gap between simple recursion and pseudo-polynomial DP. While the $O(N \cdot S)$ solution is standard, the Bitset optimization ($O(N \cdot S / 64)$) demonstrates a deep understanding of computer architecture. For massive datasets, we shift from DP to Distributed Counting + Bounded Knapsack. Whether you’re balancing load on servers or detecting financial structuring, the ability to split a set into equal parts is a fundamental skill in algorithmic design.

24. Summary

Approach Time Space Notes
Recursion $O(2^N)$ $O(N)$ TLE
Memoization $O(N \cdot S)$ $O(N \cdot S)$ Good
Tabulation $O(N \cdot S)$ $O(N \cdot S)$ Avoids recursion limit
Space Opt $O(N \cdot S)$ $O(S)$ Standard Interview Solution
Bitset $O(N \cdot S / 64)$ $O(S / 64)$ Fastest

Originally published at: arunbaby.com/dsa/0036-partition-equal-subset-sum