Solution: Partition Equal Subset Sum

Statement

Given a non-empty array of positive integers, determine if the array can be divided into two subsets so that the sum of both subsets is equal.

Constraints:

• $1 \leq$ nums.length $\leq 200$
• $1 \leq$ nums[i] $\leq 100$

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

We can solve this problem with the following two steps:

1. First, we calculate the sum of the array. If the sum of the array is odd, there can’t be two subsets with an equal sum, so we return FALSE.
2. If the sum is even, we calculate $sum/2$ and find a subset of the array with a sum equal to $sum/2$.

The naive approach is to solve the second step using recursion. In this approach, we calculate the result repeatedly every time. For example, consider an array, [1, 6, 20, 7, 8], which can be partitioned into [1, 20] and [6, 7, 8] with the sum 21. While computing the sum, we encounter 21 twice: once in the first subset (6 + 7 = 13, 13 + 8 = 21) and once in the second subset (1 + 20 = 21). However, since we’re not storing these sums, it is computed twice.

The time complexity of this approach is $O(2^n)$ ...