162. Partition Equal Subset Sum

Medium · Dynamic Programming

Given an array of positive integers `nums`, determine whether it is possible to partition the array into two subsets such that the sum of elements in both subsets is equal. Return `true` if such a partition exists, and `false` otherwise.

A partition means every element must belong to exactly one of the two subsets. The two subsets together must contain all elements of the original array.

This is a classic dynamic programming problem. The key insight is that if the total sum is odd, it's impossible to split it equally. Otherwise, you need to check if any subset sums to exactly half the total.

Examples

Example 1
Input: nums = [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11], both with sum 11.
Example 2
Input: nums = [1, 2, 3, 5]
Output: false
Explanation: The total sum is 11 (odd), so it cannot be split into two equal subsets.

Constraints