Partition Equal Subset

Check if a list of positive integers can be split into two subsets with equal sum.

dynamic-programming subset-sum memoization knapsack

Write a function `can_partition(nums)` that takes a list of positive integers `nums` and returns `True` if the list can be partitioned into two subsets with equal sum, otherwise `False`. The subsets are disjoint and together cover all elements; the order of elements doesn't matter. Each element must be used in exactly one subset.

**Input:** A list `nums` of positive integers (1 <= len(nums) <= 200, 1 <= each element <= 100).

**Output:** A boolean (`True` or `False`).

**Constraints:**
- The length of `nums` is between 1 and 200.
- Each element is a positive integer between 1 and 100.
- The time complexity should be efficient enough for the given bounds (O(n * target) is acceptable, where target is half the total sum).

**Notes:**
- If the total sum is odd, the answer is always `False`.
- If the total sum is even, we need to check whether a subset sums to exactly half the total.

Constraints

- `1 <= len(nums) <= 200`
- `1 <= nums[i] <= 100`
- Time complexity: O(n * target) where target = sum(nums)/2 (only if even).
- Space complexity: O(target).

Example

>>> can_partition([2, 2])
True

>>> can_partition([1, 5, 11, 5])
True

>>> can_partition([1, 2, 3, 5])
False

30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about the total sum: if it's odd, immediate return False. What should you check when it's even?

Try to model this as a subset-sum problem: can any subset sum to exactly half the total?

Use a boolean DP array where dp[i] means a subset sum i is achievable. Build it iteratively from the given numbers.

Iterate from the target sum down to the current number to avoid reuse of elements.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.