【递归算法】找出所有子集的异或总和再求和

题目链接文章摘要本文介绍了LeetCode题目《所有子集异或总和之和》的解法。通过分析题目要求提出三步解题思路找出所有子集、计算子集异或值、求和异或值。采用决策树模型设计回溯算法利用全局变量path和sum分别记录子集异或值和总和。详细讲解了dfs函数实现、回溯处理和递归出口等关键步骤并给出Java代码实现。该方法通过异或运算特性简化回溯操作高效计算所有子集的异或总和。一、题目解析题目定义了对数组的异或总和是怎么运算的。给我们一个数组要我们返回该数组的所有子集的异或和再求和。简单来说我们做这道题目有三个步骤找出数组的所有的子集计算所有子集中的所有数字的异或值将所有子集的异或值相加虽然看起来挺麻烦的但其实解题步骤和子集那道题目差不多我们可以把 2 和 3 的逻辑加入到 1 中。二、算法原理 代码实现决策树我们第一步就是画出决策树这里是找出数组的所有子集与上一道题目的思路一致有两种方法这里采用第二种方法作决策树。我们根据示例2来画决策树接下来我们根据决策树来设计代码。全局变量我们这里需要计算的是子集中所有元素的异或值以及异或值之和。因此定义两个 int 类型即可path 用来记录子集中所有元素的异或值ret 用来记录异或值之和。dfs 函数函数头我们这里需要通过递归遍历题目所给数组nums因此参数是数组 nums 和下标 pos。函数体在子集那道题目中我们的 dfs 函数体中做的事情是 “从当前数字往后遍历”在这里也是一样的只不过是修改的东西从集合类变成里基本数据类型。当拿到一个数字就把它与 path 进行异或然后基于这个再递归。细节问题回溯这里我们也是要在回溯的时候恢复现场的在函数体当中递归回来的时候就恢复现场。这里可以利用异或的 “抵消” 性质再次将 path 与当前数字异或就可以恢复现场了。剪枝这里同样不涉及到剪枝操作。递归出口这里不需要设置递归出口。我们更新结果是一进入 dfs 函数就更新的因为决策树的每一个节点都是结果。当函数体中的遍历结束整个递归也就结束了。代码实现public class Solution { int sum; // 记录异或值之和 int path; // 记录子集中所有元素的异或值 public int subsetXORSum(int[] nums) { dfs(nums, 0); return sum; } private void dfs(int[] nums, int pos) { sum path; // 更新结果 // 从当前数字往后遍历 for (int i pos; i nums.length; i) { path ^ nums[i]; dfs(nums, i 1); path ^ nums[i]; // 回溯时恢复现场 } } }文章到这里就告一段落啦若有错误请尽管指出完