LeetCode 2044题：统计按位或能得到最大值的子集数目（原创）

【题目描述】

2044. 统计按位或能得到最大值的子集数目

提示

给你一个整数数组 nums ，请你找出 nums 子集 按位或 可能得到的 最大值 ，并返回按位或能得到最大值的 不同非空子集的数目 。

如果数组 a 可以由数组 b 删除一些元素（或不删除）得到，则认为数组 a 是数组 b 的一个 子集 。如果选中的元素下标位置不一样，则认为两个子集 不同 。

对数组 a 执行 按位或 ，结果等于 a[0] OR a[1] OR ... OR a[a.length - 1]（下标从 0 开始）。

示例 1：

输入：nums = [3,1]
输出：2
解释：子集按位或能得到的最大值是 3 。有 2 个子集按位或可以得到 3 ：
- [3]
- [3,1]

示例 2：

输入：nums = [2,2,2]
输出：7
解释：[2,2,2] 的所有非空子集的按位或都可以得到 2 。总共有 23 - 1 = 7 个子集。

示例 3：

输入：nums = [3,2,1,5]
输出：6
解释：子集按位或可能的最大值是 7 。有 6 个子集按位或可以得到 7 ：
- [3,5]
- [3,1,5]
- [3,2,5]
- [3,2,1,5]
- [2,5]
- [2,1,5]

【解题代码】

public class CountMaxOrSubsets {

    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 1, 5};
        //int[] nums = new int[]{3, 1};
        int result = new CountMaxOrSubsets().countMaxOrSubsets(nums);
        System.out.println("The result is:" + result);
    }

    public int countMaxOrSubsets(int[] nums) {
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            max |= nums[i];
        }

        return dfs(nums, 0, 0, max);
    }

    private int dfs(int[] nums, int i, int val, int max) {
        int result = 0;
        if (i < nums.length) {
            result += dfs(nums, i + 1, val | nums[i], max);
            result += dfs(nums, i + 1, val, max);
        } else if (val == max) {
            result = 1;
        }
        return result;
    }
}

【解题思路】

        分析题目，感觉这又是一个DFS问题，首先计算出数组 nums 最大的异或值max，然后依次对数组每一位数字进行处理，分为两个分支：选择此数据进行异或运算或者不选择，一直到数组遍历结束，然后对最终的异或值进行检查，如果等于max，那么返回结果加1，否则返回0。按照此思路，很快完成代码编写，并提交LeetCode成功

【解题步骤】

1. 首先计算出数组 nums 最大的异或值max，数组最大异或值就是所有数据的进行异或的结果

   int max = nums[0];
   for (int i = 1; i < nums.length; i++) {
       max |= nums[i];
   }

2. 对所有数据进行回溯处理，回溯函数的参数分别为整数数组 nums，当前访问数据的索引值i，当前异或值val，最大的异或值max

   return dfs(nums, 0, 0, max);

3. 定义一个本地变量存储计算结果

   int result = 0;

4. 如果数组还未遍历完，那么当前数据进行递归回溯处理，分别有两个递归分支：选择此数据和不选择此数据，并分别加上计算的结果

   if (i < nums.length) {
       result += dfs(nums, i + 1, val | nums[i], max);
       result += dfs(nums, i + 1, val, max);
   } 

5. 如果数据已经遍历完，检查当前然后对最终的异或值进行检查，如果等于max，那么返回结果设置为1

    else if (val == max) {
       result = 1;
   }

6. 返回最终结果

   return result;

【思考总结】

1. 此题算法解法关键在于DFS：DFS回溯算法是深度优先搜索与回溯思想的结合：通过递归深入探索问题的某一可能路径，记录中间状态；当发现路径不符合条件时，撤销上一步选择（回溯），返回上层尝试其他路径。 它适合解决子集、排列、组合等需穷举可能解的问题，能在探索中及时剪枝无效路径，避免冗余计算，核心是“试错-回退-再试”的循环，本质是对解空间的深度优先遍历。
2. LeetCode解题之前，一定不要看题解，看了就“破功”了！