当前位置: 首页 > Web前端 > JavaScript

1863.求所有子集的异或和然后求和JavaScript【回溯】

时间:2023-03-26 20:38:51 JavaScript

数组的异或和定义为数组中所有元素按位异或的结果;如果数组为空,则异或和为0。例如,数组[2,5,6]的异或和是2XOR5XOR6=1。给定一个数组nums,请找到nums中每个子集的异或和,计算并返回这些值的和。注意:本题中,同一个元素的不同子集要多次统计。如果a是通过从b中删除一些(或可能没有)元素获得的,则数组a是数组b的子集。示例1:输入:nums=[1,3]输出:6解释:[1,3]有4个子集:-空子集的异或和为0。-[1]的异或和为1。-[3]的异或和是3。-[1,3]的异或和是1XOR3=2。0+1+3+2=6示例2:输入:nums=[5,1,6]输出:28解释:[5,1,6]共有8个子集:-空子集的异或和为0.-[5]的异或和为5。-[1]的异或和为1。-[6]的异或和为6。-[5,1]的异或和是5XOR1=4。-[5,6]的异或和是5XOR6=3。-[1,6]的异或和是1XOR6=7。-[5,1,6]的异或和是5XOR1XOR6=2。0+5+1+6+4+3+7+2=28示例3:输入:nums=[3,4,5,6,7,8]输出:480解释:每个子集的所有XOR和总和的值为480。解题思路采用回溯的基本处理方法,寻找所有可能的情况;使用累加器XOR得到所有值的总和;解题代码varsubsetXORSum=function(nums){letans=0;//回溯letbackTracing=(start,path)=>{if(path.length){//计算异或值ans+=path.reduce((acc,cur)=>acc^=cur,0)}//回溯基本处理(leti=start;i