Partition Equal Subset Sum
Asked byFacebookMicrosoftAmazonAppleGoogleWalmart Global Tech
Problem
Given an array of positive integers, determine whether it can be partitioned into two subsets with equal sums.
Examples
Example 1
Input:nums = [1,5,11,5]
Output:true
[1,5,5] and [11] both sum to 11.
Example 2
Input:nums = [1,2,3,5]
Output:false
Constraints
Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.
Solve on FeatCode →How to approach it: the 1-D Dynamic Programming pattern
Break a problem into overlapping subproblems along a single dimension — like "the answer up to index i" — solve each one once, and reuse the result instead of recomputing it.
Look for this pattern when
- A greedy or purely recursive approach recomputes the same subproblem repeatedly.
- The problem asks for a count, a minimum/maximum, or a yes/no reachability over a sequence, where the answer at position `i` depends on answers at earlier positions.
Read the full 1-D Dynamic Programming guide →
Video walkthroughs
Original problem on LeetCode ↗
More 1-D Dynamic Programming problems