Partition Equal Subset Sum (Backtracking)

Determine if an array can be split into two subsets with equal sum using backtracking.

backtracking subset-sum partition recursion pruning

Given a list of positive integers `nums`, write a function `can_partition(nums)` that returns `True` if the list can be partitioned into two subsets such that the sum of elements in both subsets is equal, and `False` otherwise. You must implement the solution using a **backtracking** approach to explore subset sums, with pruning to avoid unnecessary recursion. A valid partition exists if the total sum is even and there is a subset whose sum equals half of the total sum.

**Function signature:** `def can_partition(nums: list[int]) -> bool:`

**Details:**
- All numbers are positive integers.
- The order of elements does not matter.
- Each element must belong to exactly one of the two subsets.
- If the total sum is odd, return `False` immediately.
- Your solution must be recursive/backtracking; iterative DP is acceptable but the problem emphasizes backtracking.

**Examples:**
```python
can_partition([1, 5, 11, 5])  # True, partition {1,5,5} and {11}
can_partition([1, 2, 3, 5])   # False
can_partition([1, 2, 3, 4])   # True, partition {1,4} and {2,3}
```

Constraints

1 <= len(nums) <= 200
1 <= nums[i] <= 100
Total sum of all elements fits within a standard Python integer.
The expected time complexity is O(2^n) in the worst case, but backtracking with pruning should handle typical inputs efficiently. The constraints are small enough for a backtracking solution to pass within time limits.

Example

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

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

First check if the total sum is odd; if so, return False immediately.

Use recursion to try including or excluding each number to reach a target sum of total_sum // 2.

Before recursing, prune by skipping numbers that would exceed the target and by skipping duplicate values if helpful.

You only need to find one subset with the target sum; the rest will automatically form the other subset.

Test Results

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