2044. Count Number of Maximum Bitwise-OR Subsets

Count Number of Maximum Bitwise-OR Subsets

題目描述：給定整數陣列 nums，回傳「Bitwise OR 等於整個陣列所有元素 OR 結果」的非空子集數量。換言之，先計算 max_or = nums[0] | nums[1] | ... | nums[n-1]，再找出有多少個非空子集的 OR 值恰好等於 max_or。

解題思路：關鍵觀察：任何子集的 OR 值最大就是所有元素的 OR（max_or），因為 OR 運算只會增加位元，加入更多元素只可能保持或增加 OR 值，永遠不會減少。因此「OR 等於 max_or」的子集就是那些至少包含使得 OR 達到 max_or 所需位元的子集。

解法一（回溯）：對每個元素，選擇「加入」或「不加入」當前子集，同時追蹤當前 OR 值。當所有元素決策完畢，若當前 OR == max_or，計數加一。

解法二（位元枚舉）：枚舉所有 2^n - 1 個非空子集（用位元遮罩），計算每個子集的 OR，統計等於 max_or 的子集數。n ≤ 16，2^16 = 65536，完全可行。

時間複雜度：O(2^n)——回溯樹有 2^n 個葉節點（每個元素二選一），每個節點的工作量為 O(1)（一次 OR 運算），整體 O(2^n)。n ≤ 16，最多 65536 個葉節點，非常快。

空間複雜度：O(n)——遞迴深度為 n（每個元素對應一層），不需額外儲存子集，call stack 使用 O(n) 空間。

方法一：位元枚舉所有子集 用整數 mask 從 1 到 2^n - 1 枚舉所有非空子集，對每個子集計算其元素的 OR 值，若等於 max_or 則計數加一。時間 O(n × 2^n)（每個子集需 O(n) 計算 OR），空間 O(1)（不計輸入）。比回溯多一個 n 的係數，但程式碼最簡潔直觀。

方法二：動態規劃 dp[v] 表示 OR 值恰好為 v 的子集數量。初始 dp[0] = 1（空集合）。對每個元素 x，從高到低更新：new_dp[v | x] += dp[v]。最終答案為 dp[max_or]。時間 O(n × max_val)，空間 O(max_val)，其中 max_val ≤ 2^17 = 131072。適合需要同時統計所有 OR 值的子集分佈的場景。

方法三：數學觀察（剪枝加速） 觀察：一旦某個部分子集的 OR 已達到 max_or，其任何超集（加入更多元素）的 OR 也必然等於 max_or。若已知剩餘 k 個元素的情況，可直接將答案加上 2^k（剩餘元素任意選擇均合法）。此剪枝使回溯在最優情況下退化為 O(n)，最壞仍 O(2^n)。

1. 本題答案是否一定大於等於 1？為什麼？（提示：考慮「包含所有元素的完整集合」是否必然達到 max_or）
2. 若將 OR 換成 AND，問題變為「AND 等於所有元素 AND 的子集數量」，最小 AND 與最大 OR 的對稱性如何影響計數結果？（提示：AND 只能隨子集增大而減少）
3. 若要找出 OR 值「嚴格小於 max_or 的最大值」對應的子集數量，需要如何修改 DP 或枚舉策略？