找出所有子集的异或总和再求和 | Java刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

一、题目描述：

二、思路分析：

今天给大家分享的是一道周赛题目，目前标注的题目难度是easy，记得当时翻看该题目的评论区时，好多人都反馈这么难？其实还好，这道题没有什么特别的办法，直接按照题意求解即可，即求出所有子集，然后对求异或和就行。子集的话大家肯定都会求吧？

回溯求子集

• 直接先把回溯法求子集的代码往上一套
• 然后使用一个全局变量记录一下每个子集的异或结果
• 把每个子集的异或结果累加到全局变量sum上
• 最后返回即可。

三、AC 代码：

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    protected $sum = 0;
    function subsetXORSum($nums) {
        $len_n = count($nums);
        $this->help($nums, 0, $len_n, []);
        return $this->sum;
    }
    
    protected function help(&$nums, $start, $len_n, $temp)
    {
        if ($start > $len_n) {
            return ;
        }
        $t = 0;
        for ($i = 0; $i < count($temp); $i++) {
            $t = $t ^ $temp[$i];
        }
        $this->sum += $t;
        
        for ($i = $start; $i < $len_n; $i++) {
            $temp[] = $nums[$i];
            $this->help($nums, $i + 1, $len_n, $temp);
            array_pop($temp);
        }
    }
}

复制代码

四、总结：

有时候遇到题目没啥思路可以直接考虑暴力搞一下，说不定题目就是让你暴力弄，考察你的基础呢 ？