MediumRating 2023
2597. The Number of Beautiful Subsets
arrayhash-tablemathdynamic-programmingbacktrackingsortingcombinatorics
解題說明
The Number of Beautiful Subsets
題目描述： 給定正整數陣列 nums 和正整數 k，一個子集是「美麗的」若子集中不存在兩個元素的差的絕對值等於 k。計算所有非空美麗子集的數量。
解題思路： 將元素按模 k 分組（nums[i] % k 相同的元素放在一起）。不同組之間的元素差不可能是 k 的倍數，所以不會互相衝突，可以獨立處理。
在每組內，將元素排序後，問題變成：在一個排序序列中選擇子集，使得沒有兩個被選的元素差恰好為 k。這類似於「打家劫舍」問題——如果兩個相鄰（排序後差為 k）的值不能同時選。
對每組用 DP 計算方案數，各組方案數相乘即為總數（最後減 1 去掉空集）。
C++ 解法
複雜度分析
時間複雜度：O(n log n) — 分組和排序
空間複雜度：O(n) — 儲存分組資訊
虛擬碼
1. Group elements by (value % k)
2. For each group:
a. Sort unique values, count frequency of each
b. DP similar to house robber:
- For each value, choices = 2^count - 1 (non-empty subsets)
- If current value - previous value == k: conflict (can't both be taken)
- Track skip (not taking current) and take (taking at least one)
c. Group total = skip + take (including empty subset for this group)
3. Multiply all group totals
4. Subtract 1 (remove the global empty set)
5. Return result其他解法
-
回溯法（暴力）：枚舉所有子集（2^n 個），檢查每個子集是否美麗。時間 O(2^n * n)，適合 n <= 20 的小規模輸入。
-
回溯 + 剪枝法：先排序，回溯時使用計數陣列追蹤已選元素。選擇 nums[i] 時檢查 nums[i]-k 和 nums[i]+k 是否已在子集中。比暴力快但仍然指數級。
延伸思考
- 如果限制改為「不能有兩個元素的差為 k 或 2k」，DP 轉移需要如何調整？
- 如果 nums 中有負數，分組策略需要如何修改？
- 如果要找最大的美麗子集的大小（而非計數），如何轉化問題？