HardRating 2307
1655. Distribute Repeating Integers
arrayhash-tabledynamic-programmingbacktrackingbit-manipulationcountingbitmask
解題說明
Distribute Repeating Integers
題目描述：給定一個整數陣列 nums 和一個顧客需求陣列 quantity，其中 quantity[i] 表示第 i 個顧客需要多少個相同的整數。判斷是否能將 nums 中的整數分配給所有顧客，使每個顧客獲得恰好 quantity[i] 個相同的整數。
解題思路：首先統計 nums 中每個值的出現次數，得到頻率陣列 cnt。由於顧客數 m <= 10，可以使用 bitmask DP。定義 dp[i][mask] 表示用前 i 個頻率值能否滿足 mask 所代表的顧客子集。對於每個頻率 cnt[i]，枚舉 mask 的所有子集 sub，若 sub 對應的顧客需求總和不超過 cnt[i]，則可以從 dp[i-1][mask ^ sub] 轉移。預先計算每個子集的需求總和，避免重複計算。
C++ 解法
複雜度分析
時間複雜度：O(n × 3^m) — n 為不同數字個數，m 為顧客數（最多 10）。對每個頻率值，枚舉所有 mask 的子集，總共 3^m 個狀態轉移。
空間複雜度：O(2^m) — DP 陣列和子集和陣列各需 2^m 空間。
虛擬碼
1. Count frequency of each value in nums -> cnt array
2. Let m = len(quantity), full = (1 << m) - 1
3. Precompute subSum[mask] = sum of quantity[j] for all j in mask
4. Init dp[0] = true, all others false
5. For each frequency cnt[i]:
a. For mask from full down to 1:
- If dp[mask] already true, skip
- Enumerate all submasks sub of mask:
* If subSum[sub] <= cnt[i] and dp[mask ^ sub] is true:
Set dp[mask] = true, break
6. Return dp[full]其他解法
回溯法 + 剪枝：將顧客按需求量降序排列，嘗試將每個頻率值分配給不同顧客組合。透過排序和剪枝（跳過重複需求量）可大幅減少搜索空間，但最壞情況仍為指數級。
狀態壓縮 DP（二維版本）：使用 dp[i][mask] 明確追蹤用了前 i 個頻率值。空間為 O(n × 2^m)，但邏輯更清晰，適合理解狀態轉移。
延伸思考
- 若允許一個顧客獲得不同數字（不要求相同），問題如何變化？
- 若顧客數 m 更大（例如 20），有什麼替代策略？
- 如何修改以找出最大可滿足的顧客數量？