Decide Whether an Array Can Be Split Into Equal-Sum Subsets
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Decide Whether an Array Can Be Split Into Equal-Sum Subsets
Given an array of positive integers `nums`, return whether its occurrences can be partitioned into two subsets with equal sums. Every occurrence must belong to exactly one of the two subsets.
### Function
`bool canPartition(vector<int>& nums)`
### Example 1
```text
Input: nums = [2,3,4,5]
Output: true
```
The subsets `[2,5]` and `[3,4]` each sum to `7`.
### Example 2
```text
Input: nums = [1,2,5]
Output: false
```
The total is `8`, but no selection of the available occurrences sums to `4`.
### Constraints
- `1 <= nums.length <= 200`.
- `1 <= nums[i] <= 100`.
### Clarifications
The subsets need not be contiguous and may contain different numbers of elements. Repeated values are separate occurrences, each usable once. Return only a boolean decision, not the two subsets.
### What a Strong Answer Covers
- Equal sums while assigning every occurrence exactly once.
- Odd totals and even totals that still cannot be partitioned.
- Repeated values and a single-element input.
- Why the decision is complete and its resource bounds under the given limits.
Overview: Practice deciding whether positive integer occurrences can be partitioned into two equal-sum subsets. Preserve one-use occurrence limits and distinguish this from contiguous splitting.