zShare 博客 | leetCode第1863题找出所有子集的异或总和再求和

2021-11-20 15:40:48

摘要:描述这条题是我在等级为简单通过率第三高的一道题。我想说我不配。感觉自尊心碎了一地。一面的解析是我在leetcode解析里面找到的。在此记录题目概述一个数组的异或总和定义为数组中所有元素按位 XOR 的结果；如果数组为空，则异或总和为 0 。例如，数组 [2,5,6] 的异或总和为 2 XOR 5 XOR 6 = 1 。给你一个数组 nums ，请你求出 nums 中每个子集的异或总和，计算并返回这些值相加之和。注意...

<h2 id="h2-u63CFu8FF0"><a name="描述" class="reference-link"></a><span class="header-link octicon octicon-link"></span>描述</h2><p>这条题是我在等级为简单通过率第三高的一道题。我想说我不配。感觉自尊心碎了一地。一面的解析是我在leetcode解析里面找到的。在此记录</p>
<h2 id="h2-u9898u76EEu6982u8FF0"><a name="题目概述" class="reference-link"></a><span class="header-link octicon octicon-link"></span>题目概述</h2><p>一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。</p>
<p>例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。<br>给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。</p>
<p>注意：在本题中，元素 相同 的不同子集应 多次 计数。</p>
<p>数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。</p>
<p>示例 1：</p>
<pre><code>输入：nums = [1,3]
输出：6
解释：[1,3] 共有 4 个子集：
- 空子集的异或总和是 0 。
- [1] 的异或总和为 1 。
- [3] 的异或总和为 3 。
- [1,3] 的异或总和为 1 XOR 3 = 2 。
0 + 1 + 3 + 2 = 6
</code></pre><p>示例 2：</p>
<pre><code>输入：nums = [5,1,6]
输出：28
解释：[5,1,6] 共有 8 个子集：
- 空子集的异或总和是 0 。
- [5] 的异或总和为 5 。
- [1] 的异或总和为 1 。
- [6] 的异或总和为 6 。
- [5,1] 的异或总和为 5 XOR 1 = 4 。
- [5,6] 的异或总和为 5 XOR 6 = 3 。
- [1,6] 的异或总和为 1 XOR 6 = 7 。
- [5,1,6] 的异或总和为 5 XOR 1 XOR 6 = 2 。
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28
</code></pre><p>示例 3：</p>
<pre><code>输入：nums = [3,4,5,6,7,8]
输出：480
解释：每个子集的全部异或总和值之和为 480 。
</code></pre><p>提示：</p>
<pre><code>1 &lt;= nums.length &lt;= 12
1 &lt;= nums[i] &lt;= 20
</code></pre><p>来源：力扣（LeetCode）<br>链接：<a href="https://leetcode-cn.com/problems/sum-of-all-subset-xor-totals">https://leetcode-cn.com/problems/sum-of-all-subset-xor-totals</a></p>
<h2 id="h2-u7B54u6848u89E3u6790"><a name="答案解析" class="reference-link"></a><span class="header-link octicon octicon-link"></span>答案解析</h2><h3 id="h3-u7A0Bu5E8F"><a name="程序" class="reference-link"></a><span class="header-link octicon octicon-link"></span>程序</h3><pre><code class="lang-java">class Solution {
    int res;
    int n;
    void dfs(int val, int idx, int[] nums){
        if (idx == n){
            // 终止递归
            res += val;
            return;
        }
        // 考虑选择当前数字
        dfs(val ^ nums[idx], idx + 1, nums);
        // 考虑不选择当前数字
        dfs(val, idx + 1, nums);
    }

int subsetXORSum(int[] nums) {
        res = 0;
        n = nums.length;
        dfs(0, 0, nums);
        return res;
    }
};
</code></pre>
<h3 id="h3-u89E3u6790"><a name="解析" class="reference-link"></a><span class="header-link octicon octicon-link"></span>解析</h3><p>我们用函数dfs（val，idx）来递归枚举数组nums的子集。其中val代表当前选取部分的异或值，idx代表递归的当前位置。<br>我们用n来表示nums的长度。在进入dfs（val，idx）时，数组中[0，idx-1]部分的选取情况是已经确定的，而[idx，n）部分的选取情况还未确定。我们需要确定idx位置的选取情况，然后求解子问题dfs（val’，idx+1）。<br>此时选取情况有两种：</p>
<ul>
<li>选取，此时val’=val ^ nums[idx]，其中^代表异或运算；</li><li>不选取，此时val’=val。<br>当idx=n时，递归结束。与此同时，我们维护这些子集异或总和val的和。</li></ul>