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
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.214.188 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729264212.A.00D.html