Partition to K Equal Sum Subsets
Medium · Backtracking · Array · Backtracking · Dynamic Programming · Bit Manipulation · Bitmask
Problem
Given an integer array nums and an integer k, return true if nums can be split into k non-empty groups that all have the same sum, and false otherwise.
Every element must go into exactly one group.
Examples
Input: nums = [2,1,4,5,6], k = 3 Output: true
The groups {6}, {2, 4} and {1, 5} each add up to 6.
Input: nums = [1,2,3,4], k = 3 Output: false
The total, 10, cannot be divided into three equal whole parts.
Constraints
- 1 <= k <= len(nums) <= 16
- 1 <= nums[i] <= 10^4
- Each value appears at most 4 times in nums
Approaches
- Fill k groups by backtracking — time O(k^n), space O(n + k)
Follow-up
What if you had to return the groups, not just whether they exist? Store, for each reachable mask, the value that reached it. Walking back from the full mask lists the values in the order they were placed, and every time the running sum hits a multiple of the target a group ends.
Related problems
Start free on Cariara · Coding problems · System design studio
