Minimum Incompatibility: Bitmask DP for Subset Partitioning

You are given an array nums of n integers and an integer k. You need to distribute the n numbers into k subsets of equal size (n/k each) such that every subset contains only distinct values. The incompatibility of a subset is the difference between its maximum and minimum elements. Return the minimum possible sum of incompatibilities across all k subsets. If no valid distribution exists, return -1.

This is LeetCode 1681: Minimum Incompatibility, and it is one of the best problems for learning bitmask DP over subset partitions. The technique it teaches applies to any problem where you need to split a collection into groups while optimizing some cost function.

Why this problem matters

Subset partitioning problems appear throughout competitive programming and interviews. You need to divide items into groups, each group must satisfy constraints, and you want to minimize (or maximize) some total cost. The brute force approach of trying every possible partition is factorial in complexity, but bitmask DP brings it down to exponential, which is feasible for small n.

This problem combines two powerful techniques: bitmask DP for tracking which elements have been assigned, and submask enumeration for efficiently iterating over candidate subsets. Once you internalize these building blocks, you can apply them to problems like distributing tasks to workers, partitioning arrays into groups with constraints, and assigning items to buckets with compatibility requirements.

The key insight

Represent the state of which elements have been assigned to subsets using a bitmask. If n <= 16, there are at most 2^16 = 65536 possible states. For each state (a set of already-assigned indices), you try every valid subset of the remaining indices that has size n/k and contains only distinct values. The DP transition picks the valid subset with the lowest incompatibility and adds it to the running total.

The critical optimization is submask enumeration. Given a bitmask remain representing unassigned indices, you do not iterate over all 2^n subsets to find ones that fit. Instead, you enumerate only the submasks of remain, which guarantees you only consider subsets that use unassigned indices. Across all DP states, this enumeration costs O(3^n) total, not O(4^n).

The solution

def minimum_incompatibility(nums: list[int], k: int) -> int:
    n = len(nums)
    group_size = n // k
    full = (1 << n) - 1

    cost = {}
    for mask in range(1, full + 1):
        if bin(mask).count("1") != group_size:
            continue
        elements = [nums[i] for i in range(n) if mask & (1 << i)]
        if len(set(elements)) != group_size:
            continue
        cost[mask] = max(elements) - min(elements)

    INF = float("inf")
    dp = [INF] * (full + 1)
    dp[0] = 0

    for assigned in range(full + 1):
        if dp[assigned] == INF:
            continue
        remain = full ^ assigned
        sub = remain
        while sub > 0:
            if sub in cost:
                dp[assigned | sub] = min(dp[assigned | sub], dp[assigned] + cost[sub])
            sub = (sub - 1) & remain

    return dp[full] if dp[full] != INF else -1

The solution has two phases. First, precompute the cost of every valid subset: iterate over all bitmasks with exactly n/k bits set, extract the elements, check for duplicates, and store the incompatibility. Second, run DP over all assignment states. For each state, enumerate submasks of the remaining indices and try every valid subset.

The submask enumeration loop (sub = (sub - 1) & remain) is the engine that makes this efficient. It visits only submasks of remain, skipping irrelevant subsets entirely. When you combine a valid subset with the current assignment, you get a new state with more indices assigned.

Visual walkthrough

Bitmask  Indices  Elements
0011     {0, 1}   {1, 2}
0101     {0, 2}   {1, 1}  <- duplicate, invalid
0110     {1, 2}   {2, 1}
1001     {0, 3}   {1, 4}
1010     {1, 3}   {2, 4}
1100     {2, 3}   {1, 4}

Valid subsets of size 2 (distinct elements):
0011 -> {1, 2} -> incompat = 2 - 1 = 1
0110 -> {2, 1} -> incompat = 2 - 1 = 1
1001 -> {1, 4} -> incompat = 4 - 1 = 3
1010 -> {2, 4} -> incompat = 4 - 2 = 2
1100 -> {1, 4} -> incompat = 4 - 1 = 3

0101 -> {1, 1} -> INVALID (duplicate)

dp[0000] = 0

Try sub=0011 (cost 1): dp[0011] = 0 + 1 = 1
Try sub=1001 (cost 3): dp[1001] = 0 + 3 = 3
Try sub=1010 (cost 2): dp[1010] = 0 + 2 = 2
...

From dp[0011] = 1:
  remaining = 1100
  Try sub=1100 (cost 3): dp[1111] = 1 + 3 = 4

From dp[1010] = 2:
  remaining = 0101, but 0101 is invalid

Answer: dp[1111] = 4

To enumerate submasks of remain = 1100:
  sub = 1100  (itself)
  sub = (1100 - 1) & 1100 = 1011 & 1100 = 1000
  sub = (1000 - 1) & 1100 = 0111 & 1100 = 0100
  sub = (0100 - 1) & 1100 = 0011 & 1100 = 0000
  sub = 0 -> stop

Submasks of 1100: {1100, 1000, 0100}

The walkthrough shows how bitmask DP builds solutions from the bottom up. Starting with no indices assigned (mask = 0), each step selects a valid subset of unassigned indices and adds its cost. The DP table stores the best total cost for each assignment state, and the answer is the value at the full mask where every index has been assigned.

Complexity analysis

Time: The precomputation phase iterates over all 2^n masks, checking popcount and duplicates for each. This is O(n * 2^n). The DP phase is dominated by submask enumeration. For each mask, enumerating all submasks of its complement costs O(2^(n - popcount(mask))). Summed across all masks, this is O(3^n) by the binomial theorem: the sum of C(n, k) * 2^k for k from 0 to n equals 3^n.

Space: The DP array has 2^n entries. The cost table has at most C(n, n/k) entries, which is bounded by 2^n. Total space is O(2^n).

The building blocks

1. Subset enumeration with bitmasks

The foundation of this approach is representing subsets as integers. The bit at position i tells you whether element i is included. To check membership, test mask & (1 << i). To extract all elements, loop through bits. To combine two disjoint subsets, use bitwise OR.

for mask in range(1 << n):
    elements = []
    for i in range(n):
        if mask & (1 << i):
            elements.append(nums[i])

2. Submask iteration

Given a bitmask remain, you often need to iterate over all of its submasks (all masks that are subsets of remain). The standard technique uses the decrement-and-mask trick. Starting from remain itself, each step computes (sub - 1) & remain to jump to the next smaller submask, skipping values that are not submasks.

sub = remain
while sub > 0:
    process(sub)
    sub = (sub - 1) & remain

Edge cases

• n not divisible by k: the problem guarantees n is divisible by k, but if you want to be defensive, check n % k != 0 and return -1.
• All elements are the same: if nums has n copies of the same value and group_size > 1, no valid subset of size group_size has distinct elements. The answer is -1.
• k equals n: every subset has exactly one element, so each incompatibility is 0. The answer is always 0.
• k equals 1: the entire array must be one subset with all distinct elements. If there are duplicates, return -1. Otherwise, return max(nums) - min(nums).
• Impossible partition: when duplicate values make it impossible to form k subsets with distinct elements (e.g., a value appears more than k times), the DP naturally returns infinity, which maps to -1.

From understanding to recall

You have seen how bitmask DP transforms a combinatorial partitioning problem into a structured state-space search. The pieces are clear: precompute valid subset costs, enumerate submasks of the remaining indices, and build up the optimal partition one group at a time. But reproducing this under interview pressure is a different challenge.

The details that trip people up: remembering the submask enumeration formula (sub - 1) & remain, precomputing only masks with the right popcount, checking for distinct elements, and initializing the DP correctly. These are the kinds of things that slip away if you only read about them once.

Spaced repetition locks these patterns in. You write the submask loop, the cost precomputation, and the DP transition from scratch at increasing intervals. After a few rounds, the bitmask DP template flows out without hesitation. You do not need to re-derive the 3^n enumeration trick. You just write it.

Related posts

• Partition to K Equal Sum Subsets - A closely related subset partitioning problem that uses backtracking with pruning, giving you a second angle on dividing arrays into k groups
• Counting Bits - Builds intuition for how bit patterns relate to each other, the same kind of thinking you need for popcount checks in bitmask DP
• Subsets - The foundational subset enumeration problem that teaches the include/exclude decision tree behind every bitmask approach

CodeBricks breaks Minimum Incompatibility into its bitmask enumeration, submask iteration, and DP partitioning building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a bitmask DP problem shows up in your interview, you do not hesitate. You just write it.