2044. Count Number of Maximum Bitwise-OR Subsets
给一个整数矩阵nums
透过对nums的所有subset进行or操作找到最大值后
请问nums中有几个subset or后可以得到该最大值
思路:
先对nums进行or操作找到最大值
因为题目的限制nums的长度最长为16
就直接用backtracking找出所有subset组合后
如果or操作后的值==最大值就把answer+1
最后回传answer
golang code :
func countMaxOrSubsets(nums []int) int {
target := 0
for _, val := range nums {
target |= val
}
return backtrack(nums, target, 0)
}
func backtrack(arr []int, target, cur int) int {
res := 0
if cur == target {
res += 1
}
for i := 0; i < len(arr); i++ {
tmp := cur | arr[i]
res += backtrack(arr[i+1:], target, tmp)
}
return res
}