Command Palette

Search for a command to run...

Hectal
Problem 32.8 · Advanced DPMedium

Partition to K Equal Sum Subsets

PatternBitmask DPBacktracking

What it teaches: dp[mask] = filled amount of the current bucket after using the items in mask.

Practise it on judges as “Partition to K Equal Sum Subsets”.

The problem

Return true if nums can be split into k non-empty subsets with equal sums.

Example 1

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true

(5), (1,4), (2,3), (2,3).

Constraints

  • 1 ≤ k ≤ n ≤ 16

Pattern clues in the wording

  • → n ≤ 16
  • → Assign every item to a group

These clues point to Bitmask DP: Represent which items are used as the bits of an integer, so dp[mask] covers every subset (n up to about 20).

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
nums = [4,3,2,3,5,2,1]
k = 4
true
2
nums = [1,2,3,4]
k = 3
false

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Bitmask DP · O(2ⁿ × n)
1

Bitmask DP

Time O(2ⁿ × n) Space O(2ⁿ)

dp[mask] = current bucket fill or −1 if unreachable. From a reachable mask, add any unused item that fits; the new fill is (fill + x) mod target.

Approach 1
import java.util.Arrays;

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int x : nums) sum += x;
        if (sum % k != 0) return false;
        int target = sum / k, 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 >> i) & 1) == 1 || dp[mask] + nums[i] > target) continue;
                dp[mask | (1 << i)] = (dp[mask] + nums[i]) % target;
            }
        }
        return dp[(1 << n) - 1] == 0;
    }
}

Verdict: Reliable within the limits.

Before you submit

Edge cases and common mistakes

Test these inputs

  • An item larger than the target
  • k = 1

Mistakes people make

  • Forgetting the total must divide evenly.

Interview

Follow-up questions

How does backtracking compare?