# LeetCode 2044. Count Number of Maximum Bitwise-OR Subsets

https://leetcode.com/problems/count-number-of-maximum-bitwise-or-subsets/description/

## 題目大意

給定整數陣列 `nums`，找出其某個子集的最大可能位元或運算結果（bitwise OR），並回傳具有該最大位元或運算結果的相異非空子集數量

## 思考

最大的 bitwise OR 結果其實就是整個 `nums` 的元素都 bitwise OR 的結果

### Algo 1

我們已經知道最大值了，接著就是窮舉所有可能，找出運算結果跟最大值一樣的子集就好

class Solution
{
public:
    int countMaxOrSubsets(vector<int> &nums)
    {
        const int n = nums.size();
        const int maxOr = accumulate(nums.begin(), nums.end(), 0, bit_or<>());
        int ans = 0;

        const int maxMask = 1 << n;
        for (int mask = 1; mask < maxMask; ++mask)
        {
            int curr = 0;
            for (int i = 0; i < n; ++i)
            {
                if (mask & (1 << i))
                    curr |= nums[i];
            }

            if (curr == maxOr)
                ++ans;
        }

        return ans;
    }
};

這樣的時間複雜度會是 $O(n\cdot 2^n)$ ，空間複雜度只有 $O(1)$
(所有的可能性有 $2^n$ 種)

由於題目說 `n` 不會超過 $16$ ，所以這樣的時間複雜度是可以接受的

### Algo 2

說到窮舉所有可能，我們當然可以使用 backtracking 的技巧

class Solution
{
public:
    int countMaxOrSubsets(vector<int> &nums)
    {
        const int maxOr = accumulate(nums.begin(), nums.end(), 0, bit_or<>());
        int ans = 0;

        helper(nums, 0, 0, maxOr, ans);

        return ans;
    }

private:
    void helper(const vector<int> &nums, int i, int curr, const int &maxOr, int &ans)
    {
        if (i == nums.size())
        {
            if (curr == maxOr)
                ++ans;
            return;
        }

        helper(nums, i + 1, curr, maxOr, ans);
        helper(nums, i + 1, curr | nums[i], maxOr, ans);
    }
};

我們每次可以決定要或不要把 `nums[i]` 考慮並 bitwise OR 進去

helper(nums, i + 1, curr, maxOr, ans); // 不考慮 nums[i]
helper(nums, i + 1, curr | nums[i], maxOr, ans); // 考慮 nums[i]

這樣的時間複雜度是 $O(2^n)$ ，空間複雜度考慮到遞迴呼叫的 stack 使用的話也是 $O(2^n)$
不過正如前面所講 `n` 很小，所以這樣的演算法是 OK 的

Go 的參考解答：

func countMaxOrSubsets(nums []int) int {
    
	maxOr := 0
	for _, num := range nums {
		maxOr |= num
	}

	ans := 0
	helper(nums, 0, 0, maxOr, &ans)

	return ans
}

func helper(nums []int, i int, curr int, maxOr int, ans *int) {
	if i == len(nums) {
		if curr == maxOr {
			*ans++
		}
		return
	}

	helper(nums, i+1, curr, maxOr, ans)
	helper(nums, i+1, curr|nums[i], maxOr, ans)
}