【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 <= 161 <= nums[i] <= 105
解题方法一：二进制枚举
使用一个整数二进制的每一位代表nums数组中每个元素的选择与不选。从$0$到$2^{nums}-1$即可枚举枚举完每个元素选与不选的情况。
- 时间复杂度$O(n\times n^2)$，其中$n=len(nums)$
- 空间复杂度$O(1)$
AC代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#if defined(_WIN32) || defined(__APPLE__)
#include "_[1,2]toVector.h"
#endif
class 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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#if defined(_WIN32) || defined(__APPLE__)
#include "_[1,2]toVector.h"
#endif
class 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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#if defined(_WIN32) || defined(__APPLE__)
#include "_[1,2]toVector.h"
#endif
class 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| '''
Author: LetMeFly
Date: 2025-07-28 13:38:06
LastEditors: LetMeFly.xyz
LastEditTime: 2025-07-28 20:40:58
'''
from typing import List
class Solution:
def dfs(self, th: int, now: int) -> None:
if now == self.M:
self.ans += 1 << (len(self.nums) - th)
return
if th == len(self.nums):
return
self.dfs(th + 1, now)
self.dfs(th + 1, now | self.nums[th])
def countMaxOrSubsets(self, nums: List[int]) -> int:
self.ans = 0
self.nums = nums
self.M = 0
for t in nums:
self.M |= t
self.dfs(0, 0)
return self.ans
|
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
package main
var ans2044, maxium2044 int = 0, 0
var nums2044 []int
func 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 = nums
ans2044 = 0
maxium2044 = 0
for _, t := range nums {
maxium2044 |= t
}
dfs2044(0, 0)
return ans2044
}
|
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源