722. Two Equal Piles
Two movers must split a set of crates into two piles so that both piles weigh exactly the same. The weight of every crate is given in nums, and each crate has to go into exactly one of the two piles; a pile may not be left empty by choice, but with positive weights this never matters.
Return true when such a split exists and false otherwise. In particular an odd total weight can never be split.
Aim for time O(n * S) where S is the total weight, and extra space proportional to S (a bitset or a boolean table over half the total is enough).
Example 1
- Input:
- nums = [4,9,5,8,2,6]
- Output:
- true
- Explanation:
The total is 34, and the crates 9 and 8 weigh 17 together, leaving 4, 5, 2 and 6 which also weigh 17.
Example 2
- Input:
- nums = [7,3,11,5]
- Output:
- false
- Explanation:
The total is 26 so each pile needs 13, but no combination of 7, 3, 11 and 5 reaches 13.
Constraints
1 ≤ nums.length ≤ 200
1 ≤ nums[i] ≤ 100
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n * S)
- Space
- O(S)