给你一个长度为 n 的整数数组 nums ，这个数组中至多有 50 个不同的值。同时你有 m 个顾客的订单 quantity
，其中，整数 quantity[i] 是第 i 位顾客订单的数目。请你判断是否能将 nums 中的整数分配给这些顾客，且满足：

第 i 位顾客 **恰好 **有 quantity[i] 个整数。
第 i 位顾客拿到的整数都是 相同的 。
每位顾客都满足上述两个要求。

如果你可以分配 nums 中的整数满足上面的要求，那么请返回 true ，否则返回 false 。

示例 1：

**输入：** nums = [1,2,3,4], quantity = [2]
**输出：** false
**解释：** 第 0 位顾客没办法得到两个相同的整数。

示例 2：

**输入：** nums = [1,2,3,3], quantity = [2]
**输出：** true
**解释：** 第 0 位顾客得到 [3,3] 。整数 [1,2] 都没有被使用。

示例 3：

**输入：** nums = [1,1,2,2], quantity = [2,2]
**输出：** true
**解释：** 第 0 位顾客得到 [1,1] ，第 1 位顾客得到 [2,2] 。

提示：

n == nums.length
1 <= n <= 105
1 <= nums[i] <= 1000
m == quantity.length
1 <= m <= 10
1 <= quantity[i] <= 105
nums 中至多有 50 个不同的数字。

Problem: 1655. 分配重复整数

[TOC]

思路

用二进制集合表示待分配的顾客

解题方法

对于集合中的顾客, 必选一个数字 ps[idx] 来分配
对于数字 ps[idx] 尝试分配顾客, 如果ps[idx]无法分配任何一个顾客, 看下一个数字
相当于遍历了所有情况

Code

[]
class Solution:
    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
        c1=Counter(nums)
        ps=[]
        for i,(k,v) in enumerate(c1.items()):
            ps.append((v,i))
        ps.sort(reverse=True)
        n=len(ps)
        m=len(quantity)
        u=(1<<m)-1
        @cache
        def dfs(s, idx, take):
            if not s:
                return True
            if idx==n:
                return False
            flag=False
            takeall=ps[idx][0]
            for j in range(m):  # 尝试分配顾客j
                if s&(1<<j):
                        if take+quantity[j]<=takeall:
                            flag=dfs(s^(1<<j), idx, take+quantity[j])
                        else:
                            flag=dfs(s, idx+1, 0)
                        if flag: return True

            return False
        return dfs(u,0, 0)
        
    def canDistribute_0(self, nums: List[int], quantity: List[int]) -> bool:
        c1=Counter(nums)
        ps=[]
        for i,(k,v) in enumerate(c1.items()):
            ps.append((v,i))
        ps.sort(reverse=True)
        n=len(ps)
        m=len(quantity)
        u=(1<<m)-1
        @cache
        def dfs(s, idx, rest):
            if not s:
                return True
            if idx==n:
                return False
            flag=False
            for j in range(m):  # 尝试分配顾客j
                if s&(1<<j):
                        if rest>=quantity[j]:
                            flag=dfs(s^(1<<j), idx, rest-quantity[j])
                        else:
                            if idx+1<n:
                                flag=dfs(s, idx+1, ps[idx+1][0])
                        if flag: return True

            return False
        return dfs(u,0, ps[0][0])

1655-分配重复整数

思路

解题方法

Code