[LeetCode] 2044. Count Number of Maximum Bitwise-OR Subsets

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

leetcode - Count Number of Maximum Bitwise-OR Subsets

문제 유형: dfs, 재귀, 브루트 포스, 백트래킹, 완전탐색, 비트마스킹

문제 난이도: Medium

 

문제

Given an integer array nums, find the maximum possible bitwise OR of a subset of nums and return the number of different non-empty subsets with the maximum bitwise OR.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b. Two subsets are considered different if the indices of the elements chosen are different.

The bitwise OR of an array a is equal to a[0] OR a[1] OR ... OR a[a.length - 1] (0-indexed).

 

정수 배열 nums가 주어진다.

가능한 최대의 bitwise OR연산의 결과를 구해서, 그 결과와 똑같은 수를 만들어낼 수 있는 부분집합의 수를 구하시오.

 

풀이

부분집합의 수를 구해야 하므로, 모든 경우를 고려해야 한다.

nums의 요소 개수도 16개 이하이므로, 충분히 해결가능하다.

 

재귀를 이용해서 백트래킹을 하는 방법이 있다.

solve(현재 인덱스, bitwiseOR의 누적값, 배열)을 2^n번 호출하면 된다.

각 재귀의 내용은 현재 인덱스가 범위를 벗어나면, 누적값이 최대값과 같은지 비교하여 경우의수를 추가하면 되고,

범위 내라면, 현재 인덱스의 수를 포함하여 계산하거나, 현재 인덱스의 수를 포함하지 않는 두 경우의 갈래로 나눠서 호출하면 된다.

 

다른 방법은, 재귀를 사용하지 않는 방법이 있다.

길이가 16이므로, 16비트짜리 수를 이용해서 비트마스킹으로 풀 수 있다.

예를 들어, 8비트짜리 이진수 '00000000'은 모든 수를 포함하지 않는다는 뜻이고, '11111111'은 모든 수를 포함한다는 뜻이다.

즉, 0부터 2^n-1까지 반복해서 조합을 만들어서 풀면 된다.

 

코드

C++

재귀를 이용한 풀이

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
class Solution {
private:
    int maxOR;
    int n;
    int ans;
    void solve(int i, int masked, vector<int>& nums) {
        if(i >= n) {
            if(masked == maxOR) ans++;
            return;
        }

        solve(i+1, masked, nums);
        solve(i+1, masked | nums[i], nums);
    }
public:
    int countMaxOrSubsets(vector<int>& nums) {
        n = nums.size();
        for(const auto &num : nums) {
            maxOR |= num;
        }

        solve(0, 0, nums);

        return ans;
    }
};

 

비트마스킹을 이용한 반복풀이

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
class Solution {
public:
    int countMaxOrSubsets(vector<int>& nums) {
        int n = nums.size();
        int limit = 1 << n;
        int maxOR = 0;
        for(const auto &num : nums) {
            maxOR |= num;
        }

        int ans = 0;
        for(int i = 0; i < limit; ++i) {
            int k = i;
            int x = 0;
            for(int j = 0; j < n; ++j) {
                x |= (k % 2 == 1)? nums[j] : 0;
                k >>= 1;
            }
            if(x == maxOR) ans++;
        }
        return ans;
    }
};