Neural Mastery
← Practice
Partition Equal Subset Summedium

Partition Equal Subset Sum

medium Coding Interview Patterns 15–20 min

NumPy allowed · plain Python earns 10 bonus points

Determine if an array can be split into two subsets with identical sum using 0/1 knapsack dynamic programming.

Task

Implement can_partition_equal_subset(nums): if total sum is odd, return False. Otherwise solve 0/1 knapsack for target = sum // 2 using a boolean DP array traversed in reverse.

Function Signature

can_partition_equal_subset(nums: list[int]) -> bool

Examples

Example 1: [1, 5, 11, 5]
Input: nums = [1, 5, 11, 5]
Output: True
Example 2: [1, 2, 3, 5]
Input: nums = [1, 2, 3, 5]
Output: False

Constraints

  • 1 <= len(nums) <= 200
  • 1 <= nums[i] <= 100
Python3Saved ✓
def can_partition_equal_subset(nums: list[int]) -> bool:
"""nums: array of positive integers.
Determine if the array can be partitioned into two subsets such that the
sum of elements in both subsets is equal."""
# Your implementation here
pass

Case 1: [1, 5, 11, 5]
Input: nums = [1, 5, 11, 5]
Expected: True
Case 2: [1, 2, 3, 5]
Input: nums = [1, 2, 3, 5]
Expected: False