Problem statement

https://leetcode.com/problems/distribute-repeating-integers/

Solution

Let us precalculate sums of all subsets first for speed. Let us define our state as dfs(i, mask), where i is index not of customer, but Counter(nums):

Imagine we have Counter(nums) = 10, 5 and quantities = 5,7,3, then we first try to distribute 10: on different bitmasks: 000, 001, 010, 011, 100, 101, 110, 111, here we can choose 000, 001, 010, 001, 101, 011: 000 coressponds to empty, 010 to 7, 101 to 5 + 3 and so on).

Complexity

For each state and mask we need to iterate over all submasks and we can do it efficiently in the way it is shown in code. It can be proven, that time complexity of this code is $O(m\cdot 3^m)$, space complexity is $O(m \cdot 2^m)$.

Code

class Solution:
    def canDistribute(self, a, customers):
        m = len(customers)
        a = sorted(Counter(a).values())[-m:]
        n = len(a)
        
        mask_sum = [0]*(1<<m)
        for mask, i in product(range(1<<m), range(m)):
            if (1 << i) & mask:
                mask_sum[mask] += customers[i]
                    
        
        @lru_cache(None)
        def dfs(i, mask):
            if mask == 0: return True
            if i == n:    return False
            
            submask = mask
            while submask:
                if mask_sum[submask] <= a[i] and dfs(i+1, mask ^ submask):
                    return True
                submask = (submask-1) & mask
            return dfs(i+1, mask)
                
        return dfs(0, (1<<m) - 1)