Partition to K Equal Sum Subsets — Problem & Solution
Partition to K Equal Sum Subsets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Partition to K Equal Sum Subsets is a medium coding problem on dynamic programming, backtracking and bitmask, asked in Amazon, Google, Microsoft and LinkedIn interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Backtracking, Bitmask
- Asked at: Amazon, Google, Microsoft, LinkedIn
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums and an integer k, decide whether the elements can be split into exactly k non-empty groups whose sums are all equal.
Every element must go into exactly one group; the groups need not be contiguous. Return true if such a split exists and false otherwise.
Example 1
Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: `[5]`, `[1,4]`, `[2,3]`, `[2,3]` all sum to 5.
Example 2
Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: The total 10 is not divisible by 3.
Example 3
Input: nums = [6,2,2,2,6,6], k = 3
Output: true
Constraints
1 <= k <= nums.length <= 161 <= nums[i] <= 10^4Each value occurs at most 4 times in nums
Hints for Partition to K Equal Sum Subsets
Hint 1
If the total is not a multiple of
k, or some element exceedstotal / k, the answer is immediatelyfalse.Hint 2
With at most 16 elements, the set of elements already used fits in a bitmask.
Hint 3
Fill groups one at a time: for each used-set, the only thing that matters is how full the current group is (
sum of used % target). Mark reachable masks and check the full mask.
How to solve Partition to K Equal Sum Subsets
Fill the groups one after another. Once you know which elements are used, the fill level of the open group is determined (sum(used) mod target), so a DP over the 2^n subsets is enough.
Approach
- Let
target = total / k; returnfalseif the division is inexact or the largest element exceedstarget. - Sort ascending.
dp[mask]= fill level of the open group after usingmask, or -1 ifmaskcannot be reached;dp[0] = 0. - For each reachable mask, try every unused element
i: ifdp[mask] + nums[i] <= target, the maskmask | 1<<iis reachable with level(dp[mask] + nums[i]) % target. Because the array is sorted, stop at the first element that overflows. - Return whether the full mask is reachable.
Why it works
Any valid partition can be listed group by group, each group's elements in any order, and every prefix of that listing keeps the open group at or below target — so the full mask is reached. Conversely each transition only ever closes a group when it hits target exactly, so reaching the full mask means the elements were cut into groups of sum target, and there are exactly total / target = k of them.
Complexity
- Time —
O(2^n · n) - Space —
O(2^n)
Pitfalls
- Forgetting the early
max > targetcheck is harmless for the DP but the divisibility check is essential. - The groups are not contiguous — a prefix-sum approach does not work.
- Plain backtracking without pruning (skip identical buckets) can blow up on adversarial inputs.
Reference solution
Python
from typing import List
def canPartitionKSubsets(nums: List[int], k: int) -> bool:
total = sum(nums)
if total % k != 0:
return False
target = total // k
a = sorted(nums)
if a[-1] > target:
return False
n = len(a)
dp = [-1] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
cur = dp[mask]
if cur < 0:
continue
for i in range(n):
if mask & (1 << i):
continue
if cur + a[i] > target:
break
nm = mask | (1 << i)
if dp[nm] < 0:
dp[nm] = (cur + a[i]) % target
return dp[(1 << n) - 1] == 0Java
public static boolean canPartitionKSubsets(int[] nums, int k) {
int total = 0;
for (int v : nums) total += v;
if (total % k != 0) return false;
int target = total / k;
int[] a = nums.clone();
Arrays.sort(a);
int n = a.length;
if (a[n - 1] > target) return false;
int full = (1 << n) - 1;
int[] dp = new int[full + 1];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int mask = 0; mask <= full; mask++) {
int cur = dp[mask];
if (cur < 0) continue;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) continue;
if (cur + a[i] > target) break;
int nm = mask | (1 << i);
if (dp[nm] < 0) dp[nm] = (cur + a[i]) % target;
}
}
return dp[full] == 0;
}C++
bool canPartitionKSubsets(vector<int>& nums, int k) {
int total = 0;
for (int v : nums) total += v;
if (total % k != 0) return false;
int target = total / k;
vector<int> a(nums.begin(), nums.end());
sort(a.begin(), a.end());
int n = a.size();
if (a[n - 1] > target) return false;
int full = (1 << n) - 1;
vector<int> dp(full + 1, -1);
dp[0] = 0;
for (int mask = 0; mask <= full; mask++) {
int cur = dp[mask];
if (cur < 0) continue;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) continue;
if (cur + a[i] > target) break;
int nm = mask | (1 << i);
if (dp[nm] < 0) dp[nm] = (cur + a[i]) % target;
}
}
return dp[full] == 0;
}JavaScript
var canPartitionKSubsets = function(nums, k) {
var total = 0;
for (var i = 0; i < nums.length; i++) total += nums[i];
if (total % k !== 0) return false;
var target = total / k;
var a = nums.slice().sort(function(x, y) { return x - y; });
var n = a.length;
if (a[n - 1] > target) return false;
var full = (1 << n) - 1;
var dp = new Array(full + 1).fill(-1);
dp[0] = 0;
for (var mask = 0; mask <= full; mask++) {
var cur = dp[mask];
if (cur < 0) continue;
for (i = 0; i < n; i++) {
if (mask & (1 << i)) continue;
if (cur + a[i] > target) break;
var nm = mask | (1 << i);
if (dp[nm] < 0) dp[nm] = (cur + a[i]) % target;
}
}
return dp[full] === 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming · Backtracking