Partition to K Equal Sum Subsets
Partition to K Equal Sum Subsets is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Backtracking Patterns pattern, in the Combination Sum subpattern.
Problem statement
Given nums, an array of positive integers, and k, determine whether all elements can be divided into exactly k nonempty groups. Each element must be assigned to one group, and no element may be used more than once.
Every group must have the same sum. Return true if such a partition is possible; otherwise, return false. The order of the groups and the order of elements within a group are irrelevant.
Example 1:
Input: nums = [6,10,14,18], k = 2 Output: true Explanation: The total is 48, so each group must sum to 24. The elements can be split into {6, 18} and {10, 14}.
Example 2:
Input: nums = [2,2,2,2,2,2,2,2,9], k = 5 Output: false Explanation: The total is 25, so each group would need sum 5, but the value 9 alone exceeds that target.
Example 3:
Input: nums = [3,5,6,7,9,10], k = 2 Output: true Explanation: Each group must sum to 20. One valid partition is {3, 7, 10} and {5, 6, 9}.
Constraints:
- 4 <= nums.length <= 16 - 1 <= nums[i] <= 10^4 - 1 <= k <= nums.length - The sum of all values in nums is divisible by k - The sum of all values in nums is at most 10^4
Topics and companies
Topics: Array, Backtracking, Depth-First Search, Memoization.
How to practise Partition to K Equal Sum Subsets on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n * 2^n) time and O(2^n) space.
Open Partition to K Equal Sum Subsets in the code editor, or read the Partition to K Equal Sum Subsets editorial for a worked solution with its approach and complexity analysis.
Where Partition to K Equal Sum Subsets sits in the DSA pattern sheet
- Backtracking Patterns pattern guide
- Combination Sum subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Partition to K Equal Sum Subsets
Other problems that use the same Combination Sum and Backtracking Patterns techniques:
- Combination Sum — Medium, same subpattern
- Combination Sum II — Medium, same subpattern
- Check if Word Can Be Placed In Crossword — Medium, same pattern
- Combinations — Medium, same pattern
- Generate Parentheses — Medium, same pattern
- Letter Combinations of a Phone Number — Medium, same pattern