2275. Largest Combination With Bitwise AND Greater Than Zero
解題說明
Largest Combination With Bitwise AND Greater Than Zero
題目描述：給定正整數陣列 candidates，從中選取若干元素（至少一個）組成一個組合，使得組合中所有元素的按位 AND 大於 0。求這樣的組合的最大長度。
解題思路（逐位計數）：
關鍵觀察：一個組合的 AND > 0，當且僅當存在至少一個 bit 位 b，使得組合中所有元素在第 b 位均為 1（這樣 AND 的第 b 位為 1，AND 結果 > 0）。
等價轉化：要使 AND > 0，需要找到某個 bit 位 b，使得在第 b 位為 1 的元素數量最多。所有在第 b 位為 1 的元素共同 AND 的第 b 位仍為 1，因此 AND > 0。
演算法：
- 對每個 bit 位 b（0 到 23，因為 candidates[i] ≤ 10⁷ < 2²⁴）：
- 統計陣列中有多少個元素的第 b 位為 1（即
(candidates[i] >> b) & 1 == 1）。
- 統計陣列中有多少個元素的第 b 位為 1（即
- 所有 bit 位中計數最大的值即為答案。
正確性：選取所有在第 b* 位（計數最大的 bit）為 1 的元素，其 AND 的第 b* 位為 1，因此 AND > 0。且無法透過跨多個 bit 位來獲得更多元素（每個 bit 選法都是獨立的最優解）。
C++ 解法
複雜度分析
時間複雜度：O(n · B) — n 為陣列長度，B 為 bit 位數（此題 B = 24）；整體為 O(24n) = O(n)。
空間複雜度：O(1) — 只使用常數個輔助變數，無需額外資料結構。
虛擬碼
1. ans = 0.
2. For bit in 0..23:
a. count = 0.
b. For each num in candidates:
- If (num >> bit) AND 1 == 1: count++.
c. ans = max(ans, count).
3. Return ans.其他解法
方法二：雜湊表計數（同效但不同實作）
對每個元素分解其所有設為 1 的 bit，在雜湊表中對每個 bit 位計數 +1。最後取雜湊表中最大值。效果與方法一相同，但因元素的 bit 數不固定（稀疏時較快），時間 O(n · popcount_avg)，程式碼稍長。
方法三：按位分組 + 貪心
對每個 bit 位 b，將陣列分成「第 b 位為 1」和「第 b 位為 0」兩組，第一組的大小即為以第 b 位共用 bit 的最大組合大小。這與逐位計數完全等價，是同一演算法的不同描述方式。
方法四：暴力子集枚舉
枚舉所有 2^n 個子集，對每個子集計算 AND，若 > 0 則更新最大長度。時間 O(2^n · n)，空間 O(1)。當 n = 10⁵ 時完全不可行，僅適用於 n ≤ 20 的小測資驗證。
延伸思考
- 若
candidates[i]的值域擴大到 10¹⁸（64 位整數），只需將 bit 範圍從 24 改為 63，演算法複雜度如何變化？ - 若條件改為「組合的 AND 值恰好等於某個目標值 target」，問題如何轉化？逐位計數技巧是否仍然適用？
- 此題等價於求某個 bit 位的最大出現頻率，與 LC 2044（Count Pairs Whose Sum is Less than Target）等計數類題目有何不同？逐位計數技巧在哪類問題中最有效？