LeetCode 2044.统计按位或能得到最大值的子集数目：二进制枚举/DFS回溯(剪枝)

【LetMeFly】2044.统计按位或能得到最大值的子集数目：二进制枚举/DFS回溯(剪枝)

力扣题目链接：https://leetcode.cn/problems/count-number-of-maximum-bitwise-or-subsets/

给你一个整数数组 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]

 

提示：

• 1 <= nums.length <= 16
• 1 <= nums[i] <= 105

解题方法一：二进制枚举

使用一个整数二进制的每一位代表nums数组中每个元素的选择与不选。从$0$到$2^{nums}-1$即可枚举枚举完每个元素选与不选的情况。

• 时间复杂度$O(n\times n^2)$，其中$n=len(nums)$
• 空间复杂度$O(1)$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-07-28 13:38:06* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-07-28 18:51:34*/
#if defined(_WIN32) || defined(__APPLE__)
#include "_[1,2]toVector.h"
#endifclass Solution {
public:int countMaxOrSubsets(vector<int>& nums) {int maxium = 0;for (int t : nums) {maxium |= t;}int ans = 0;int n = nums.size(), mask = 1 << n;for (int i = 0; i < mask; i++) {int thisVal = 0;for (int j = 0; j < n; j++) {if (i >> j & 1) {thisVal |= nums[j];}}ans += thisVal == maxium;}return ans;}
};

解题方法二：回溯DFS

写一个函数dfs(th, now)代表已经选(或不选)过前$th$个元素且总或值为$now$的情况。

如果已经选了$len(nums)$个，则判断$now$是否为$nums$所有元素或的结果并返回。如果是则ans++。

否则，可以不选当前元素并递归（dfs(th, now)），也可以选当前元素并递归（dfs(th+1, now | nums[i]）。

• 时间复杂度$O(n^2)$，其中$n=len(nums)$
• 空间复杂度$O(n)$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-07-28 19:30:16* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-07-28 19:50:18*/
#if defined(_WIN32) || defined(__APPLE__)
#include "_[1,2]toVector.h"
#endifclass Solution {
private:int ans = 0;int maxium = 0;vector<int> nums;void dfs(int th, int now) {if (th == nums.size()) {ans += now == maxium;return;}dfs(th + 1, now);dfs(th + 1, now | nums[th]);}
public:int countMaxOrSubsets(vector<int>& nums) {for (int t : nums) {maxium |= t;}this->nums = move(nums);dfs(0, 0);return ans;}
};

解题方法三：回溯DFS+小剪枝

有没有办法提前退出dfs函数呢？有。当当前的或结果已经为最大或结果的时候，后面的元素不论或与不或都不改变最终结果了。此时假设还剩$k$个元素，那么就说明后面还有$1<<k$种选法。

• 时间复杂度$O(n^2)$，其中$n=len(nums)$
• 空间复杂度$O(n)$

时空复杂度不变，但很多时候可以提前退出。

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-07-28 19:30:16* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-07-28 19:51:20*/
#if defined(_WIN32) || defined(__APPLE__)
#include "_[1,2]toVector.h"
#endifclass Solution {
private:int ans = 0;int maxium = 0;vector<int> nums;void dfs(int th, int now) {if (now == maxium) {ans += 1 << (nums.size() - th);return;}if (th == nums.size()) {return;}dfs(th + 1, now);dfs(th + 1, now | nums[th]);}
public:int countMaxOrSubsets(vector<int>& nums) {for (int t : nums) {maxium |= t;}this->nums = move(nums);dfs(0, 0);return ans;}
};

Python

'''
Author: LetMeFly
Date: 2025-07-28 13:38:06
LastEditors: LetMeFly.xyz
LastEditTime: 2025-07-28 20:40:58
'''
from typing import Listclass Solution:def dfs(self, th: int, now: int) -> None:if now == self.M:self.ans += 1 << (len(self.nums) - th)returnif th == len(self.nums):returnself.dfs(th + 1, now)self.dfs(th + 1, now | self.nums[th])def countMaxOrSubsets(self, nums: List[int]) -> int:self.ans = 0self.nums = numsself.M = 0for t in nums:self.M |= tself.dfs(0, 0)return self.ans

Java

/** @Author: LetMeFly* @Date: 2025-07-28 13:38:06* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-07-28 20:43:13*/
class Solution {private int ans = 0;private int M = 0;private int[] nums;private void dfs(int th, int now) {if (now == M) {ans += 1 << (nums.length - th);return;}if (th == nums.length) {return;}dfs(th + 1, now);dfs(th + 1, now | nums[th]);}public int countMaxOrSubsets(int[] nums) {this.nums = nums;for (int t : nums) {M |= t;}dfs(0, 0);return ans;}
}

Go

/** @Author: LetMeFly* @Date: 2025-07-28 13:38:06* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-07-28 20:31:11*/
package main// import "fmt"var ans2044, maxium2044 int = 0, 0
var nums2044 []intfunc dfs2044(th, now int) {if now == maxium2044 {ans2044 += 1 << (len(nums2044) - th)return}if th == len(nums2044) {return}dfs2044(th + 1, now)dfs2044(th + 1, now | nums2044[th])
}func countMaxOrSubsets(nums []int) int {nums2044 = numsans2044 = 0maxium2044 = 0for _, t := range nums {maxium2044 |= t}dfs2044(0, 0)return ans2044
}// func main() {
//     fmt.Println(countMaxOrSubsets([]int{2, 2, 2}))
// }

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源