🔗 🟢 1863. Sum of All Subset XOR Totals 1372

tags: `Weekly Contest 241` `暴力法(Brute Force)` `回溯(Backtracking)` `位運算(Bit Manipulation)` `狀態壓縮` `數學(Math)`

雖然是 Easy 題，但 $O(n)$ 的解法可不簡單。

題意

一個陣列的 異或總和(XOR Total) 定義為陣列中所有元素按位 XOR 的結果，如果陣列為空，則異或總和為 0 。

給定一個陣列 $nums$ ，請你求出 $nums$ 中每個子集的 異或總和 ，計算並返回這些值相加之和。

限制

$1 \leq nums.length \leq 12$
$1 \leq nums[i] \leq 20$

思路

方法一：暴力法(Brute Force) + 回溯(Backtracking) / 狀態壓縮

暴力枚舉所有子集，計算每個子集的 XOR 和。比較直覺的方法是可以用回溯法來實現，但可以注意到陣列的長度最多只有 $12$ ，而每個元素都只有在或不在子集中兩種狀態，所以可以把每個元素的狀態用二進位表示，這樣就可以用一個長度為 $12$ 的二進位數來表示一個子集，並且將枚舉子集轉換成枚舉數字，這就是狀態壓縮。

直接枚舉 $[0, 2^n)$ 之間的所有數字，對於每個數字，對應的二進位數中的每一位，如果該位是 1，則將對應的元素異或到當前子集的 XOR 和中，最後將當前子集的 XOR 和加到答案中即可。此外，由於空子集的 XOR 和為 0，所以其實可以從 $1$ 開始枚舉。

複雜度分析

時間複雜度： $O(n \cdot 2^n)$ ，枚舉所有子集需要 $O(2^n)$ 的時間，對於每個子集，需要 $O(n)$ 的時間計算 XOR 和。
空間複雜度： $O(1)$ 。

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(1 << n): # 枚舉所有子集，狀態壓縮
            cur = 0 # 當前子集的 XOR 和
            for j in range(n):
                if i & (1 << j): # 當前元素是否在子集中
                    cur ^= nums[j]
            ans += cur
        return ans

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        for (int i = 1; i < (1 << n); i++) { // 枚舉所有子集，狀態壓縮
            int cur = 0; // 當前子集的 XOR 和
            for (int j = 0; j < n; j++){ // 當前元素是否在子集中
                if (i & (1 << j)) cur ^= nums[j];
            }
            ans += cur;
        }
        return ans;
    }
};

方法二：數學(Math) + 位運算(Bit Manipulation)

由於 XOR 是按位運算，所以可以按位考慮每個子集中該位 $1$ 的個數。

若該子集中該位 $1$ 的個數為奇數，則該位的 XOR 值為 $1$
若該子集中該位 $1$ 的個數為偶數，則該位的 XOR 值為 $0$

接著從元素中該位的值來考慮所有子集中該位的 XOR 和，可以得到以下結論：

若所有元素中的該位皆為 $0$ ，則在所有 $2^n$ 個子集中，該位的 XOR 和顯然為 $0$
若至少有一個元素中的該位為 $1$ ，則總共有 $2^(n-1)$ 個子集中該位 $1$ 的個數為奇數、 $2^(n-1)$ 個子集中該位 $1$ 的個數為偶數。

結論 2. 的證明如下：

假設陣列中該位為 $1$ $1$ 的元素個數為 $m$ $m$ ，那麼子集中包含 $k$ $k$ 個 $1$ $1$ 的個數為 $(k \leq m \leq n)$ $(k \leq m \leq n)$ ：
$2^{n-m}\binom{m}{k}$
- 包含奇數個 $1$ 的子集數量為：
  $2^{n-m} \sum_{k \text { is odd, } 0 \leq k \leq m}\binom{m}{k}$
- 包含偶數個 $1$ 的子集數量為：
  $2^{n-m} \sum_{k \text { is even, } 0 \leq k \leq m}\binom{m}{k}$
可以得出包含奇數個 $1$ 的子集數量和包含偶數個 $1$ 的子集數量相等，故兩者皆為 $2^{n-1}$ 。

若所有元素的第 $i$ 位中至少有一個元素的該位為 $1$ ，則該位對答案的貢獻為 $2^{n-1} \times 2^i$ ，所以只要判斷在所有元素中是否有一個元素的該位為 $1$ ，就能計算對答案的貢獻。可以計算所有元素的 OR 值，最後乘上 $2^{n-1}$ ，也就是左移 $n-1$ 位即可。

複雜度分析

時間複雜度： $O(n)$ ，計算所有元素的 OR 值需要 $O(n)$ 的時間。
空間複雜度： $O(1)$ 。

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        for x in nums:
            res |= x
        return res << (n - 1)

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        for (int x : nums) ans |= x;
        return ans << (n - 1);
    }
};