題目資訊

• 題目編號: 1863
• 題目連結: Sum of All Subset XOR Totals
• 主題: Array, Math, Backtracking, Bit Manipulation, Combinatorics, Enumeration

題目敘述

數組的 XOR 總和 被定義為其所有元素的位元運算 XOR，若數組為空，則結果為 0。

• 例如，數組 [2,5,6] 的 XOR 總和 為 2 XOR 5 XOR 6 = 1。

給定一個數組 nums，返回 nums 所有子集的 XOR 總和的總和。

注意：具有相同元素的子集應被計算多次。

如果數組 a 可以透過刪除數組 b 的一些（可能為零個）元素得到，則數組 a 為數組 b 的子集。

範例 1:

輸入: nums = [1,3]
輸出: 6
解釋: [1,3] 的 4 個子集是:
- 空子集的 XOR 總和為 0。
- [1] 的 XOR 總和為 1。
- [3] 的 XOR 總和為 3。
- [1,3] 的 XOR 總和為 1 XOR 3 = 2。
0 + 1 + 3 + 2 = 6

範例 2:

輸入: nums = [5,1,6]
輸出: 28
解釋: [5,1,6] 的 8 個子集是:
- 空子集的 XOR 總和為 0。
- [5] 的 XOR 總和為 5。
- [1] 的 XOR 總和為 1。
- [6] 的 XOR 總和為 6。
- [5,1] 的 XOR 總和為 5 XOR 1 = 4。
- [5,6] 的 XOR 總和為 5 XOR 6 = 3。
- [1,6] 的 XOR 總和為 1 XOR 6 = 7。
- [5,1,6] 的 XOR 總和為 5 XOR 1 XOR 6 = 2。
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

範例 3:

輸入: nums = [3,4,5,6,7,8]
輸出: 480
解釋: 每個子集的 XOR 總和的總和是 480。

約束條件:

• $1 \leq \text{nums.length} \leq 12$
• $1 \leq \text{nums}[i] \leq 20$

直覺

本問題要求計算給定數組 nums 每個子集的 XOR 總和。子集的 XOR 總和是通過對子集中所有元素進行按位 XOR 操作得到的。直觀地，由於一個包含 $n$ 個元素的集合將有 $2^n$ 個子集，我們需要一種有效的方法來探索所有可能的子集並計算它們的 XOR 總和，因為即使對於中等大小的數組，可能的子集數也是指數級的。

解法

解法使用遞歸回溯法來探索輸入數組 nums 的所有可能子集。具體過程如下：

1. 遞歸探索：我們定義了一個遞歸輔助函數 calculateXORSum，它將嘗試一次構建一個元素所有可能的子集。該函數使用三個主要參數：index 用來跟蹤數組中的位置，currentXOR 用來保存當前子集的 XOR 總和，result 用來累積所有子集的 XOR 總和。

2. 基礎情況：當 index 達到數組的大小時，遞歸停止，這表明已考慮完當前子集的所有元素。此時，計算得到的 currentXOR 被加到 result 中，實際上捕捉到了這個子集的 XOR 總和。

3. 遞歸決策：對於數組中的每個元素，函數面臨一個決策：要么將當前元素包含在正在構建的子集中，要么不包含。

   • 包含當前元素：遞歸調用繼續，將 currentXOR 與當前元素 nums[index] 的 XOR 傳入。
   • 不包含當前元素：遞歸調用在不修改 currentXOR 的情況下繼續，基本上跳過當前元素。

4. 遍歷所有元素：對每個元素的這種雙重選擇保證了所有子集都被生成。通過覆蓋包含和不包含元素的所有可能組合，計算並累積每個子集的 XOR 總和。

這種遞歸策略有效地對每個子集進行了一次探索，並使用時間複雜度 $O(2^n)$ 累積它們的 XOR 總和，其中 $n$ 是 nums 中的元素個數。鑒於約束條件，這種方法在合理的時間限制內是可行的。

程式碼

C++

class Solution {
public:
    // 函數用於計算數組中每個子集的所有 XOR 總和
    int subsetXORSum(vector<int>& nums) {
        // 初始化結果以儲存 XOR 總和
        int result = 0;
        // 呼叫輔助函數從第一個索引開始探索所有子集
        calculateXORSum(nums, 0, 0, result);
        return result;
    }

    // 輔助函數計算並累加子集的 XOR 總和
    void calculateXORSum(vector<int>& nums, int index, int currentXOR, int& result) {
        // 如果到達數組末尾，將當前的 XOR 總和加到結果中
        if (index == nums.size()) {
            result += currentXOR;
            return;
        }
        
        // 將當前元素包含在子集中並遞迴
        calculateXORSum(nums, index + 1, currentXOR ^ nums[index], result);
        // 將當前元素從子集中排除並遞迴
        calculateXORSum(nums, index + 1, currentXOR, result);
    }
};

Python

class Solution:
    # 計算數組的每個子集的 XOR 總和之和的函數
    def subsetXORSum(self, nums):
        # 初始化結果以存儲 XOR 總和
        result = 0
        # 呼叫輔助函數來探索從第一個索引開始的所有子集
        self.calculateXORSum(nums, 0, 0, result)
        return result

    # 輔助函數來計算並累加子集的 XOR 總和
    def calculateXORSum(self, nums, index, currentXOR, result):
        # 如果到達數組末尾，將當前的 XOR 總和加到結果中
        if index == len(nums):
            result += currentXOR
            return
        
        # 將當前元素包含在子集中並遞迴
        self.calculateXORSum(nums, index + 1, currentXOR ^ nums[index], result)
        # 將當前元素排除在子集之外並遞迴
        self.calculateXORSum(nums, index + 1, currentXOR, result)

複雜度分析

• 時間複雜度: $O(2^n)$

  時間複雜度為 $O(2^n)$，其中 $n$ 是輸入陣列 nums 中元素的數量。這是因為該演算法使用遞歸方法探索 nums 的所有可能子集。nums 中的每個元素可以包含在子集中或排除在子集之外，從而形成 $2^n$ 個可能的子集。對於每一個子集，皆會進行一次遞歸呼叫，這對時間複雜度有貢獻。

• 空間複雜度: $O(n)$

  空間複雜度為 $O(n)$，這主要是因為 calculateXORSum 函數使用的遞歸棧空間。遞歸呼叫棧的最大深度等於 nums 中元素的數量，即 $n$。每次遞歸呼叫會在棧中添加一個框架，但除了呼叫棧之外，沒有其它隨著輸入大小增長的空間被使用。