The problem
Given an array of positive integers nums, return true if it can be split into two groups with equal sums.
Examples
01
- Input
nums = [1, 5, 11, 5]
- Output
true
02
- Input
nums = [1, 2, 3, 5]
- Output
false
Constraints
- 1 ≤ nums.length ≤ 200
- 1 ≤ nums[i] ≤ 100
The idea
Two equal groups each sum to half the total. So an odd total is impossible, and otherwise the question is: does some selection of the numbers add up to half?
Let can[s] say whether some of the numbers seen so far add up to s, starting with only can[0] true. Each new number x makes s reachable if s − x already was. Update s from high to low, so the can[s − x] being read is still from before x — otherwise x could be used twice. Stop as soon as can[half] is true.
- Time
- O(n × half)
- Space
- O(half)
Solution · every language run against every case
class Solution: def canPartition(self, nums: List[int]) -> bool: total = sum(nums) if total % 2: return False # an odd total cannot split into two equal halves half = total // 2 # can[s]: can some of the numbers seen so far add up to s? can = [True] + [False] * half for x in nums: for s in range(half, x - 1, -1): # downwards, so x is used at most once can[s] = can[s] or can[s - x] if can[half]: return True return can[half]