Partition to K Equal Sum Subsets

Medium Recursion & Backtracking Pick / Not-Pick Original on LeetCode

Reported atLinkedIn

Partition to K Equal Sum Subsets is a medium recursion & backtracking problem solved with the pick / not-pick pattern. The best approach, optimal (bitmask dp), runs in O(n · 2^n) time and O(2^n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (backtracking into k buckets) up.

Problem

You are given an integer array nums and an integer k. Decide whether the elements can be split into k non-empty groups whose sums are all equal.

Every element must belong to exactly one group, and the groups do not need to be contiguous. Return true if such a split exists, otherwise false.

Examples

Example 1

Input
nums = [6, 1, 5, 3, 3, 4, 2], k = 3
Output
true
Why
The total is 24, so each group needs 8: [6, 2], [5, 3] and [1, 3, 4].

Example 2

Input
nums = [7, 2, 2, 1], k = 2
Output
false
Why
Each group would need 6, but 7 alone is already larger than 6.

Example 3

Input
nums = [5, 5, 5, 5], k = 4
Output
true
Why
Every element forms its own group with sum 5.

Constraints

  • 1 <= k <= nums.length <= 16
  • 1 <= nums[i] <= 10^4

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (backtracking into k buckets)O(k^n)O(n + k)
Optimal (bitmask DP)O(n · 2^n)O(2^n)

1Brute force (backtracking into k buckets)

TimeO(k^n)In the worst case every number can go into any of the k buckets; the prunings cut this down a lot in practice but not in theory.
SpaceO(n + k)The bucket sums plus a recursion stack of depth n.

Compute target = total / k. Sort the numbers and place them from largest to smallest into k buckets, trying every bucket that still has room. If the last number is placed, every bucket is full. Two cheap prunings keep it practical: never try two buckets that currently hold the same sum (they lead to identical subtrees), and stop as soon as a number failed in an empty bucket.

  1. If total % k != 0, return false. Let target = total / k.
  2. Sort nums; if the largest is above target, return false.
  3. place(idx): if idx < 0, return true.
  4. For each bucket b: skip it if adding nums[idx] overflows target or an earlier bucket has the same sum.
  5. Add nums[idx] to bucket b and recurse on idx - 1; on success return true, otherwise undo.
  6. If bucket b was empty before the undo, break: other empty buckets would fail the same way.
class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % k != 0) return false;
        int target = total / k;
        Arrays.sort(nums);
        if (nums[nums.length - 1] > target) return false;
        return place(nums, nums.length - 1, new int[k], target);
    }

    private boolean place(int[] nums, int idx, int[] buckets, int target) {
        if (idx < 0) return true;
        for (int b = 0; b < buckets.length; b++) {
            if (buckets[b] + nums[idx] > target) continue;
            boolean dup = false;
            for (int c = 0; c < b; c++) {
                if (buckets[c] == buckets[b]) { dup = true; break; }
            }
            if (dup) continue;
            buckets[b] += nums[idx];
            if (place(nums, idx - 1, buckets, target)) return true;
            buckets[b] -= nums[idx];
            if (buckets[b] == 0) break;
        }
        return false;
    }
}

2Optimal (bitmask DP)

TimeO(n · 2^n)Each of the 2^n masks tries at most n numbers.
SpaceO(2^n)One integer per mask.

Fill the buckets one after another instead of in parallel. Then the only thing that matters is which numbers are used: their total mod target is exactly how full the current bucket is. Let dp[mask] be that fill level if the numbers in mask can be placed this way, or -1 if they cannot. A number may be added only if it fits in the current bucket. The answer is whether the full mask is reachable.

  1. If total % k != 0, return false. Let target = total / k.
  2. dp = array of size 2^n filled with -1; dp[0] = 0.
  3. For each mask in increasing order with dp[mask] >= 0, try every unused index i.
  4. If dp[mask] + nums[i] <= target, set dp[mask | 1 << i] = (dp[mask] + nums[i]) % target (if not already set).
  5. Return dp[2^n - 1] == 0.
class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % k != 0) return false;
        int target = total / k;
        int n = nums.length;
        int[] dp = new int[1 << n];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] < 0) continue;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) continue;
                if (dp[mask] + nums[i] > target) continue;
                int next = mask | (1 << i);
                if (dp[next] < 0) dp[next] = (dp[mask] + nums[i]) % target;
            }
        }
        return dp[(1 << n) - 1] == 0;
    }
}

Edge cases to test

  • k = 1: the whole array is one group, always true
  • k = nums.length: true only when every element is equal
  • A total that is not divisible by k is immediately false
  • One element larger than total / k makes it impossible
  • The total divides evenly but the numbers still cannot be split, like [5, 5, 5, 3, 3, 3] with k = 2

Hints

Hint 1

Every group must sum to exactly total / k. If that is not a whole number, or some element is bigger than it, the answer is false.

Hint 2

Think of k buckets of capacity total / k. Place the numbers one by one and backtrack when a number fits nowhere. Placing big numbers first fails faster.

Hint 3

With at most 16 numbers, the set of used numbers fits in a bitmask. If you always fill one bucket at a time, the progress inside the current bucket is just (sum of used numbers) mod target, so a mask alone describes the state.

FAQ

What is the best time complexity for Partition to K Equal Sum Subsets?

Optimal (bitmask DP) runs in O(n · 2^n) time and O(2^n) extra space. Each of the 2^n masks tries at most n numbers.

Which pattern does Partition to K Equal Sum Subsets use?

It is a recursion & backtracking problem that uses the pick / not-pick pattern. Other problems with the same pattern: Generate all binary strings without consecutive 1's, Subsets (2 choices per element), Subsets II.

Is there a brute force solution for Partition to K Equal Sum Subsets?

Yes. Brute force (backtracking into k buckets) takes O(k^n) time and O(n + k) space. Compute target = total / k.

Which edge cases should I test for Partition to K Equal Sum Subsets?

k = 1: the whole array is one group, always true; k = nums.length: true only when every element is equal; A total that is not divisible by k is immediately false; One element larger than total / k makes it impossible; The total divides evenly but the numbers still cannot be split, like [5, 5, 5, 3, 3, 3] with k = 2.