Distribute Repeating Integers: Bitmask DP over Customer Subsets

LeetCode Distribute Repeating Integers (Problem 1655) asks you to determine whether you can distribute values from an array to satisfy a list of customer orders, where each customer needs a specific number of copies of the same value.

The problem

You are given an array nums of integers (possibly with duplicates) and an array quantity of length m, where quantity[i] is the number of copies of any single value that customer i needs. Each customer must receive all their copies from one value, and no two customers can share the same value. Return true if every customer can be satisfied, false otherwise.

The key observation is that the actual values in nums do not matter. Only the frequency counts matter. If nums = [1,1,2,2], the useful information is that you have two values, each appearing twice. You need to assign each customer to one of these frequency "buckets" so that the bucket has enough copies to fulfill the customer's demand.

The brute force approach

The naive solution is to try every possible assignment of values to customers. For each customer, pick a value, subtract the customer's demand from that value's count, and recurse. If all customers are satisfied, return true. If any assignment fails, backtrack and try a different value.

This works but is painfully slow. With n distinct values and m customers, you try up to n choices for each of m customers, giving O(n^m) branches. For the problem constraints (up to 50 distinct values and 10 customers), that can be billions of branches. Pruning helps, but the worst case is still rough.

The key insight

Instead of iterating over customers one at a time, think about subsets of customers. For each frequency count, you can ask: which subset of customers can this count satisfy? A count c can satisfy a subset S of customers if the total demand of S (the sum of quantity[i] for all i in S) is at most c.

This reframes the problem as a bitmask DP. Represent the set of customers as a bitmask of m bits. dp[i][mask] answers: using the first i frequency counts, can you satisfy exactly the customer subset represented by mask?

Step-by-step walkthrough

Let's trace through the algorithm with nums = [1,1,2,2] and quantity = [2,2].

The full mask 11 (both customers) ends up true after processing both counts. That means every customer can be satisfied, so we return true.

The code

from collections import Counter

def canDistribute(nums, quantity):
    counts = list(Counter(nums).values())
    m = len(quantity)
    full = (1 << m) - 1

    subset_sum = [0] * (1 << m)
    for mask in range(1, 1 << m):
        lowest = mask & (-mask)
        bit = lowest.bit_length() - 1
        subset_sum[mask] = subset_sum[mask ^ lowest] + quantity[bit]

    dp = [False] * (1 << m)
    dp[0] = True

    for c in counts:
        new_dp = dp[:]
        for mask in range(1, 1 << m):
            if new_dp[mask]:
                continue
            sub = mask
            while sub > 0:
                if subset_sum[sub] <= c and dp[mask ^ sub]:
                    new_dp[mask] = True
                    break
                sub = (sub - 1) & mask
        dp = new_dp

    return dp[full]

The outer loop iterates over each frequency count. For each count, we try every mask and enumerate its submasks. If the submask's total demand fits in the current count and the remaining customers (mask XOR submask) were already satisfiable, then the full mask becomes satisfiable.

Complexity analysis

Where n is the number of distinct values and m is the number of customers.

The bitmask DP runs in O(n * 3^m) because for each of the n counts, the total work across all masks and their submask enumerations is O(3^m). With m at most 10, that is 59,049 operations per count, and with up to 50 counts, the total is roughly 3 million operations. That runs comfortably within time limits. The space is O(2^m) for the DP array and the precomputed subset sums.

The building blocks

Bitmask subset enumeration

The core technique is enumerating all submasks of a given bitmask. The loop sub = mask; while sub > 0: ... sub = (sub - 1) & mask visits every non-empty subset of mask exactly once. This same trick appears in problems like Partition to K Equal Sum Subsets (bitmask DP variant) and any problem where you need to split a set into groups with constraints.

Subset sum precomputation

By building subset_sum[mask] incrementally (each mask's sum equals the sum of the mask without its lowest bit, plus the quantity at that bit position), you avoid recomputing sums inside the DP loop. This incremental approach is the same idea behind the DP in Counting Bits, where each number's answer depends on a smaller number with one bit cleared.

Edge cases

• Single customer: if any count is at least quantity[0], return true. The bitmask DP handles this correctly since there is only one non-empty mask.
• More customers than distinct values: if m exceeds the number of distinct values, you cannot satisfy every customer (since each customer needs a unique value). The DP naturally returns false because you run out of counts before filling all bits.
• A customer needs more copies than any single count provides: the DP skips submasks whose demand exceeds every count, so this customer can never be assigned.
• All customers need 1 copy: reduces to checking whether there are at least m distinct values. The DP still works, but you could short-circuit with a simple count check.

From understanding to recall

The bitmask DP pattern for distributing items across constrained groups is a powerful tool, but it has several moving parts: precomputing subset sums, the submask enumeration loop, and the DP transition. In an interview, forgetting any one of these pieces means you cannot produce the solution. Spaced repetition helps you internalize the submask enumeration trick and the 3^m analysis so they come to mind automatically when you see a problem involving subset assignments.

The bitmask DP building block is one of roughly 60 reusable patterns that cover hundreds of LeetCode problems. Drilling it independently, writing the submask loop and DP transition from scratch, and spacing your reps over days and weeks is how you move from "I understand bitmask DP" to "I can write it cold."

Related posts

• Partition to K Equal Sum Subsets - Another problem that distributes elements across groups with equal constraints, solvable with both backtracking and bitmask DP
• Partition Equal Subset Sum - The simpler two-group partition problem, showing how subset sum DP works without bitmasks
• Counting Bits - Uses the same "clear lowest bit" trick for incremental computation that powers the subset sum precomputation here