619. K Equal Teams
A coach has n players, and nums[i] is the skill score of player i. She wants to split all of them into exactly k non-empty teams so that every team has the same total score.
Return true if such a split exists and false otherwise. Trying every assignment of players to teams costs about k^n steps. A solution that remembers which players are already placed (a bit mask) and how full the current team is needs only about 2^n * n.
Example 1
- Input:
- nums = [4,3,2,3,5,2,1], k = 4
- Output:
- true
- Explanation:
The total is 20, so every team needs 5:
5,1 + 4,2 + 3and2 + 3.
Example 2
- Input:
- nums = [7,7,7], k = 2
- Output:
- false
- Explanation:
The total is 21, which cannot be split into two equal totals.
Example 3
- Input:
- nums = [6,2,2,2], k = 2
- Output:
- true
- Explanation:
Each team must reach 6:
6alone and2 + 2 + 2.
Constraints
- 1 ≤
k≤nums.length≤ 15 - 1 ≤
nums[i]≤ 104
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 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(2^n * n)
- Space
- O(2^n)