Day 22：1863. Sum of All Subset XOR Totals

今日题目

题目连结：1863. Sum of All Subset XOR Totals
题目主题：Array, Backtracking, Bit Manipulation

虽然昨天的题目也有提到 Bit ，不过实作时其实不太需要用到相关知识，今天的题目在实作时会用到相关知识，所以会分享一下关於 Bit 的基本概念。

简单说说 Bit

Bit 又称为二进制，简单说的话 Bit 会看到的数字不是 1 就是 0，通常我们平常看到的数字是十进制，最基本的概念是需要了解如何将十进制转成二进制，先看这张表：

先从绿色的部份开始看，1 是2的零次方，2 是2的1次方，基本上二进制里面 1 每往左走一格就是多一个次方，例如 100000 就是 2的 6 次方，转成 10 进制就是 32。

如果要用二进制表示十进制的 3 或 5 会怎麽看？用 3 当例子是 0011，只要把 1 拆开来看就很好理解，拆开来会变成 0010 跟 0001 那就是 2 跟 1，加起来就是 3。

Bit 逻辑运算

这边介绍几种基本的 Bit 逻辑运算：

1. AND
   范例： 3 AND 5
   
   上图中可以看到这样运算出来结果是0001，当两个数字转成二进制以後，同样位置出现 1 ，就会继续将 1 保留到下面，其他都转成 0。

2. OR
   范例： 3 OR 5
   
   上图中可以看到这样运算出来结果是0111，当两个数字转成二进制以後，只要两个数字其中一个位置有 1，就会继续将 1 保留到下面，其他都保持 0。

3. XOR
   范例： 3 XOR 5
   
   上图中可以看到这样运算出来结果是0110，当两个数字转成二进制以後，同样位置出现 1 ，会将数字改为 0 放到下面，其他只要其中一个有 1 就保留到下面。

题目解说

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

题目会给一个数字阵列，目的是将这个阵列中的所有子集合的 XOR 总和加总後回传。

Ex. [2, 5, 6]的XOR总和等於 1，2 XOR 5 XOR 6 运算过程如下：

1. 2 XOR 5 = 7 看成二进制如右 010 XOR 101 = 111。
2. 111 二进制转成十进制是 7。
3. 7 XOR 6 = 1 看成二进制如右 111 XOR 110 = 001。
4. 最後 001 二进制转十进制是 1。

约束：

• 1 <= nums.length <= 12
• 1 <= nums[i] <= 20

范例1

输入: nums = [1,3]
输出: 6
解说: [1,3] 总共会有四个子集如下:
- 空的子集总和就是 0。
- [1] 只有一个数字总和直接是 1。
- [3] 只有一个数字总和直接是 3。
- [1,3] 1 XOR 3 = 2, 看成二进制 01 XOR 11 = 10，10 二进制转十进制等於 2。
最後加总 -> 0 + 1 + 3 + 2 = 6

范例2:

输入: nums = [5,1,6]
输出: 28
解说: [5,1,6] 总共会有四个子集如下:
- 空的子集总和就是 0
- [5] 只有一个数字总和直接是 5.
- [1] 只有一个数字总和直接是 1.
- [6] 只有一个数字总和直接是 6.
- [5,1] 5 XOR 1 = 4, 看成二进制 101 XOR 001 = 100，100 二进制转十进制等於 4。
- [5,6] 5 XOR 6 = 3, 看成二进制 101 XOR 110 = 011，011 二进制转十进制等於 3。
- [1,6] 1 XOR 6 = 7, 看成二进制 001 XOR 110 = 111，111 二进制转十进制等於 7。
- [5,1,6] 5 XOR 1 XOR 6 = 2. 看成二进制 101 XOR 001 XOR 110 = 010，010 二进制转十进制等於 2。
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

范例3

输入: nums = [3,4,5,6,7,8]
输出: 480

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

文字描述

1. 写一个递回方法传入以下：
   • 目标阵列
   • 目前总和
   • stack 存放要计算的子集合
2. 进入递回方法：
   • 将 stack 目前的子集计算XOR总和，加至目前总和
   • 跑一个for回圈继续计算所有子集
3. 最终递回方法会回传所有子集的XOR总和的加总。

图解过程

范例：[3, 4, 5, 6, 7]

上图中，每一个节点都是一个子集合，越下层代表这个子集是越多值组成的，如最左边最下面的 7 是从最上面的 3 走下来的，这个子集合为 [3, 4, 5, 6, 7]。而中间的 4 -> 5 -> 6 -> 7 就代表 [4, 5, 6, 7]，最上面的 3 这个节点就代表 [3] 这个子集合，最後一个例子可以看到最左上角有一个空的代表空的子集合，如同前面范例空的子集也会算在里面。

再来看看每个节点左边的红色数字，代表这个子集合的XOR总和，建议各位也可以跟着都算一次，会更清楚每个算出来的结果是怎麽来的。

最後可以看到下面的红色加总，就是将所有子集合的XOR总和的加总，这个范例得到的结果会是 112。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

class Solution:
    def total(self, nums, index = 0, sumValue = 0, stack = []):
        # 将目前的子集合加总
        tmpValue = 0
        for value in stack:
            tmpValue ^= value
        sumValue += tmpValue
        
        # 找出所有子集合
        for i in range(index, len(nums)):
            stack.append(nums[i])
            sumValue = self.total(nums, i+1, sumValue, stack) 
            stack.pop()
    
        # 回传目前总和
        return sumValue
    
    def subsetXORSum(self, nums: List[int]) -> int:
        return self.total(nums)

希望您今天能了解到...

1. Bit 基本概念
2. 1863. Sum of All Subset XOR Totals 的解题方法

若内容有什麽问题或建议欢迎一起交流：）
感谢您今天愿意花时间看完这篇文章~~~~

Next：1974. Minimum Time to Type Word Using Special Typewriter