Largest Subset Sum Divisible by Three
Company: Garena
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Select any elements of nums, each at most once, so their sum is divisible by 3. Return the largest such sum. The empty selection is allowed and contributes 0.
```cpp
class Solution {
public:
int maxSumDivThree(vector<int>& nums);
};
```
### Examples
**Example 1:**
```text
Input: nums = [2,4,5]
Output: 9
Explanation: Choose4 and5. The total11 is not divisible by3, and the next achievable multiple cannot exceed9.
```
**Example 2:**
```text
Input: nums = [1,1]
Output: 0
Explanation: No nonempty subset sum is divisible by3.
```
### Constraints
- nums contains 1 to 40000 integers.
- Every value is between 1 and 10000, inclusive.
### Contract considerations
The input values are positive, and selecting no element is explicitly valid.
```hint Read the boundary condition
Must selected elements be contiguous, and may an input occurrence be selected more than once?
```
### Boundary reminders
The input values are positive, and selecting no element is explicitly valid.
Overview: Largest Subset Sum Divisible by Three. Select any elements of nums, each at most once, so their sum is divisible by3.