Partition to K Equal Sum Subsets

Partition to K Equal Sum Subsets

What is this problem about?

The Partition to K Equal Sum Subsets problem asks whether an array can be divided into k subsets with equal sum. This coding problem uses bitmask DP with memoization for small n (≤16) or backtracking with pruning for larger inputs. The array, bitmask, memoization, backtracking, bit manipulation, and dynamic programming interview pattern is comprehensively tested.

Why is this asked in interviews?

Microsoft, Meta, Amazon, LinkedIn, Google, Bloomberg, and Adobe ask this because it generalizes subset sum to k equal parts — significantly harder than k=2 (Partition Equal Subset Sum). The bitmask DP approach with memoization is elegant for small n.

Algorithmic pattern used

Bitmask DP with memoization. dp[mask] = the running sum of the current incomplete subset given which elements are already used. Initialize dp[0]=0. For each mask: let curr_sum = dp[mask] % target. Try adding each unused element: if curr_sum + arr[i] ≤ target, set dp[mask | (1<<i)] = dp[mask] + arr[i]. Answer: dp[(1<<n)-1] == target * (k-1) (or equivalently check sum).

Backtracking alternative: fill k buckets recursively with pruning (sort descending, skip duplicates).

Example explanation

arr=[4,3,2,3,5,2,1], k=4. Total=20. Target=5. Check partitions: {5},{4,1},{3,2},{3,2}. Each sums to 5. Return true.

arr=[1,2,3,4], k=3. Total=10. 10%3≠0. Return false.

Common mistakes candidates make

• Not checking total%k==0 first.
• Backtracking without sorting (misses pruning opportunities).
• Incorrect bitmask DP state (must track sum modulo target, not just used elements).
• Not handling the case where any single element > target.

Interview preparation tip

Partition to K Equal Sum Subsets is harder than k=2 because you can't use simple boolean DP. For k≤4 and n≤16, bitmask DP with memoization is elegant. For larger n, backtracking with sorting (descending) and duplicate skipping is effective. Always check the necessary conditions first: total%k==0, no element > total/k. Practice both approaches to handle any constraint variant.