Chapter 18: The 0/1 Knapsack - Partition Equal Subset Sum

So far, the knapsack-style problems we've encountered (like "Coin Change") have allowed us to use an unlimited supply of each item. This is known as the unbounded knapsack problem. Now, we'll explore its equally important sibling: the 0/1 Knapsack problem. Here, for each item, we have only two choices: either include it in our solution (take it once) or don't include it at all.

A fantastic problem that perfectly illustrates this pattern is LeetCode's "Partition Equal Subset Sum" (Problem #416). While it might not look like a knapsack problem at first, a simple reframing reveals its true nature.

The Problem:

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.

For example:

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

• Output: true

• Explanation: The array can be partitioned as [1, 5, 5] and [11].

• nums = [1, 2, 3, 5]

• Output: false

• Explanation: The array cannot be partitioned into equal sum subsets.

The Key Insight: Reframing the Problem

If we are to partition the array into two subsets with equal sums, then the sum of each subset must be exactly half of the total sum of the entire array.

1. Calculate the total_sum of all numbers in nums.

2. If total_sum is odd, it's impossible to split it into two equal integer halves. We can immediately return False.

3. If total_sum is even, the problem is transformed into: "Can we find a subset of nums that sums up to target = total_sum / 2?"

This is a classic 0/1 Knapsack problem. Our "items" are the numbers in nums, and our "knapsack capacity" is the target sum. We need to determine if we can pick some of these items to perfectly fill the knapsack.

Approach 1: The Recursive Solution

Our recursive function can_partition(index, current_sum) will return True if a sum of current_sum can be achieved using numbers from nums[index:].

The state transitions are:

1. Base Case 1: If current_sum == 0, we've found a valid subset. Return True.

2. Base Case 2: If index >= len(nums) or current_sum < 0, we've gone too far without reaching the target. Return False.

3. Recursive Step: For the number nums[index]:

   • Option A: Include nums[index]. Recurse with can_partition(index + 1, current_sum - nums[index]).

   • Option B: Exclude nums[index]. Recurse with can_partition(index + 1, current_sum).

The result is True if either option returns True.

from typing import List

def canPartition_recursive(nums: List[int]) -> bool:
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False
    target = total_sum // 2

    def solve(index, current_sum):
        if current_sum == 0:
            return True
        if index >= len(nums) or current_sum < 0:
            return False

        # Option A: Include nums[index] OR Option B: Exclude nums[index]
        return solve(index + 1, current_sum - nums[index]) or solve(index + 1, current_sum)

    return solve(0, target)

# Trying it out
# print(canPartition_recursive([1, 5, 11, 5])) # True
# This will be too slow for large inputs.

Approach 2: Memoization with a Decorator (Top-Down DP)

The state is (index, current_sum), which is perfect for caching.

import functools
from typing import List

class Solution:
    def canPartition_memoized(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 != 0:
            return False
        target = total_sum // 2

        @functools.lru_cache(maxsize=None)
        def solve(index, current_sum):
            if current_sum == 0:
                return True
            if index >= len(nums) or current_sum < 0:
                return False

            return solve(index + 1, current_sum - nums[index]) or solve(index + 1, current_sum)

        return solve(0, target)

# Trying it out
# solver = Solution()
# print(solver.canPartition_memoized([1, 5, 11, 5])) # True

Time complexity is O(n * target) since there are n * target possible states.

Approach 3: Iteration (Bottom-Up DP)

The most common way to solve knapsack problems iteratively is with a DP set or boolean array. Let dp be a set that stores all the possible sums we can create using the numbers we've seen so far.

1. Initialize dp as a set containing just 0 (we can always make a sum of 0 by picking no items).

2. Iterate through each num in nums.

3. For each num, create a new set next_dp. For every s in the current dp, add s and s + num to next_dp.

4. Update dp = next_dp.

5. After iterating through all numbers, check if target is in our final dp set.

def canPartition_iterative(nums: List[int]) -> bool:
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False
    target = total_sum // 2

    dp = {0}
    for num in nums:
        next_dp = set()
        for s in dp:
            next_dp.add(s)
            next_dp.add(s + num)
        dp = next_dp

    return target in dp

# Trying it out
# print(canPartition_iterative([1, 5, 11, 5])) # True

This is a clean and intuitive bottom-up solution. The space complexity can be up to O(target), and the time complexity is O(n * target).

Conclusion

"Partition Equal Subset Sum" is the quintessential entry point to the 0/1 Knapsack pattern. The key was the initial insight: transforming the problem into finding a subset that sums to a specific target. This chapter highlights a critical distinction from the "unbounded" knapsack problems like "Coin Change." In the 0/1 pattern, our recursive step always moves to index + 1, ensuring each item is considered only once. This simple change in the recursive call is what defines this entire class of problems.