Partition to K Equal Sum Subsets

Medium
1475.

Partition to K Equal Sum Subsets

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.

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 <= 16
  • 1 <= nums[i] <= 10^4
  • Each value occurs at most 4 times in nums
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var canPartitionKSubsets = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 16
  • 1 <= nums[i] <= 10^4
  • Each value occurs at most 4 times in nums

Hints for Partition to K Equal Sum Subsets

  1. Hint 1

    If the total is not a multiple of k, or some element exceeds total / k, the answer is immediately false.

  2. Hint 2

    With at most 16 elements, the set of elements already used fits in a bitmask.

  3. 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

  1. Let target = total / k; return false if the division is inexact or the largest element exceeds target.
  2. Sort ascending. dp[mask] = fill level of the open group after using mask, or -1 if mask cannot be reached; dp[0] = 0.
  3. For each reachable mask, try every unused element i: if dp[mask] + nums[i] <= target, the mask mask | 1<<i is reachable with level (dp[mask] + nums[i]) % target. Because the array is sorted, stop at the first element that overflows.
  4. 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 > target check 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] == 0

Java

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