Given an array of positive integers nums, return true if you can split it into two subsets whose sums are equal, and false otherwise. Every element must go into exactly one of the two subsets.
[1,5,5] and [11] both sum to 11.- 1 <= nums.length <= 200
- 1 <= nums[i] <= 100
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries all 2^n ways to assign elements to the two sides. Notice that if one subset sums to total / 2, the other automatically does too, so the question becomes subset sum with target total / 2. State: dp[i][s] = can a subset of the first i numbers sum to s. Recurrence: skip number i (dp[i-1][s]) or take it (dp[i-1][s - x]). Base case: dp[0][0] = true. The table is n x target; it shrinks to one boolean array if we iterate s downwards, so each number is used at most once.
Algorithm
- Compute the total. If it is odd, return
false. Lettarget = total / 2. - Create a boolean array
dpof sizetarget + 1withdp[0] = true. - For each number
x, forsfromtargetdown tox, setdp[s] = dp[s] or dp[s - x]. - Return
dp[target](you may stop early as soon as it becomes true).
O(n * target)Space: O(target)[1, 2] could wrongly reach target by reusing values.class Solution: def canPartition(self, nums: List[int]) -> bool: total = sum(nums) if total % 2: return False # odd total target = total // 2 dp = [False] * (target + 1) # dp[s]: some subset sums to s dp[0] = True for x in nums: for s in range(target, x - 1, -1): # backwards: each x used once if dp[s - x]: dp[s] = True if dp[target]: return True return dp[target]