Divide All Values into Equal-Sum Groups
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Decide whether every element of nums can be assigned to exactly k nonempty groups so that all group sums agree. Each array position must be used once.
```cpp
class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k);
};
```
### Examples
**Example 1:**
```text
nums = [1,1,2,2], k = 2
Output: true
Explanation: The groups [1,2] and [1,2] each sum to 3.
```
**Example 2:**
```text
nums = [2,2,2,4], k = 2
Output: false
Explanation: Each group would need sum 5, but all available values are even.
```
### Constraints
- Array length n and group count obey 1 <= k <= n <= 16.
- Each value lies between 1 and 10000 inclusive.
- Any particular value occurs between one and four times.
### Contract considerations
Use all positions, require nonempty groups and preserve exactly k groups.
```hint Read the boundary condition
Which information about a partially used set is determined by its total?
```
### Boundary reminders
Use all positions, require nonempty groups and preserve exactly k groups.
Overview: Divide All Values into Equal-Sum Groups. Decide whether every element of nums can be assigned to exactly k nonempty groups so that all group sums agree.
