Simple yes case
Input
[1, 5, 11, 5]
Output
True
The array can be partitioned into [1,5,5] and [11], both sum to 11.
Full lesson preview
Check if an array can be partitioned into equal subset sums
Determine whether an array of positive integers can be split into two subsets with equal sum (the Partition problem).
Python practice17 minDynamic ProgrammingIntermediateLast updated March 29, 2026
Problem statement
Given a non-empty list of positive integers, determine if it can be partitioned into two subsets such that the sum of elements in both subsets is equal. Return True if such a partition exists, otherwise return False. Implement an efficient dynamic programming approach (subset-sum) using either a boolean DP set or bitset-style optimization.
Function signature: can_partition(nums: List[int]) -> bool
Notes: If the total sum is odd, it's immediately impossible. Aim for O(n * target) worst-case but optimize with early exits and using a set to track reachable sums.
Task
Implement a dynamic programming solution that returns True if the array can be partitioned into two subsets with equal sum, otherwise False.
Examples
Input format
A list of positive integers, e.g. [1, 5, 11, 5].
Output format
Boolean True or False indicating whether an equal-sum partition exists.
Constraints
1 <= len(nums) <= 200. Each num is a non-negative integer; typical values up to 10^5 are allowed. Total sum may be up to ~2e7 in worst cases; use an approach that avoids unnecessary work and exits early when possible.
Samples
Sample 1
Input
[1, 2, 3, 5]
Output
False
Total sum is 11 (odd), so can't partition into equal subsets.