Partition Equal Subset Sum - Video Solutions

Problem Overview: Given an integer array nums, determine whether it can be split into two subsets whose sums are equal. The problem reduces to checking if a subset exists whose sum equals half of the total array sum.

Approach 1: Recursive with Memoization (Top-Down DP) (Time: O(n * target), Space: O(n * target))

Start by computing the total sum of the array. If the sum is odd, equal partition is impossible. Otherwise the goal becomes finding a subset that adds up to target = total / 2. Use recursion to decide for each index whether to include the current number or skip it. Without optimization this creates an exponential search tree, but memoization caches results for (index, remaining_sum) so the same state is never recomputed. A hash map or 2D memo table stores whether a state leads to a valid subset. This turns the brute-force search into a manageable top‑down dynamic programming solution.

The recursive state transitions are straightforward: either subtract the current value from the remaining target or move to the next index unchanged. If any path reaches exactly zero, a valid subset exists. This pattern appears frequently in dynamic programming problems that originate from subset or knapsack decisions.

Approach 2: Dynamic Programming (Subset Sum DP) (Time: O(n * target), Space: O(target))

This approach converts the subset search into a bottom‑up DP problem. Instead of recursion, maintain a boolean DP array where dp[s] indicates whether a subset with sum s is achievable. Initialize dp[0] = true because a sum of zero is always possible using an empty subset. Then iterate through each number in the array and update the DP table in reverse order so each number is used at most once.

For every value num, update states from target down to num. If dp[s - num] was previously reachable, mark dp[s] as reachable. This effectively simulates choosing or skipping each number without storing full subset combinations. The reverse iteration is critical; it prevents the same element from being reused multiple times.

The algorithm finishes once all numbers are processed. If dp[target] is true, a subset exists whose sum equals half of the total, meaning the array can be partitioned into two equal subsets. This is the classic subset‑sum formulation used across many dynamic programming interview problems.

Recommended for interviews: Interviewers typically expect the bottom‑up subset sum DP with the 1D boolean array. It demonstrates that you recognized the reduction to a knapsack-style problem and optimized space from O(n * target) to O(target). Explaining the recursive memoization version first shows clear reasoning about the decision tree, while implementing the optimized DP solution shows strong problem‑solving and performance awareness.