A variation on the Knapsack Problem: how to solve the Partition Equal Subset Sum problem in Java

3 months ago

Previously, I wrote about solving the Knapsack Problem (KP) with dynamic programming. You can read about it here.

Today I want to discuss a variation of KP: the partition equal subset sum problem. I first saw this problem on Leetcode — this was what prompted me to learn about, and write about, KP.

This is the problem statement (reproduced partially without examples):

Given a non-empty array 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 the full problem statement, with constraints and examples, check out the Leetcode problem.

Dynamic programming

Like with KP, we’ll be solving this using dynamic programming. Since this is a variation of KP, the logic and methodology is largely similar.

Solution

We will house our solution in a method that returns a boolean — true if the array can be partitioned into equal subsets, and false otherwise.

Step 1: Guarding against odd array sum

Trivially, if all the numbers in the array add up to an odd sum, we can return false. We only proceed if the array adds up to an even sum.