[JAVA 문제 풀이] 405. Count Number of Maximum Bitwise-OR Subsets

Count Number of Maximum Bitwise-OR Subsets - LeetCode

Can you solve this real interview question? Count Number of Maximum Bitwise-OR Subsets - 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).   Example 1: Input: nums = [3,1] Output: 2 Explanation: The maximum possible bitwise OR of a subset is 3. There are 2 subsets with a bitwise OR of 3: - [3] - [3,1] Example 2: Input: nums = [2,2,2] Output: 7 Explanation: All non-empty subsets of [2,2,2] have a bitwise OR of 2. There are 23 - 1 = 7 total subsets. Example 3: Input: nums = [3,2,1,5] Output: 6 Explanation: The maximum possible bitwise OR of a subset is 7. There are 6 subsets with a bitwise OR of 7: - [3,5] - [3,1,5] - [3,2,5] - [3,2,1,5] - [2,5] - [2,1,5]   Constraints: * 1 <= nums.length <= 16 * 1 <= nums[i] <= 105

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

정수 배열 'nums'가 주어졌을 때, 'nums'의 부분 집합의 최대 비트 단위 OR을 구하고,
최대 비트 단위 OR을 가진 서로 다른 비어 있지 않은 부분 집합의 수를 반환합니다.

배열 'a'는 배열 'b'의 일부 (아마도 0일 수도 있는) 요소를 삭제하여
'b'에서 'a'를 얻을 수 있는 경우 배열 'b'의 하위 집합입니다.
선택한 요소의 인덱스가 다른 경우 두 하위 집합이 다른 것으로 간주됩니다.

배열 'a'의 비트 단위 OR은 'a[0] 또는 a[1] 또는 ... 
또는 a[a. length - 1] (0-indexed)'과 같습니다.

제약 조건:
* 1 <= nums.length <= 16
* 1 <= nums [i] <= 105

내가 작성한 코드

public class Solution {
    int maxOr = 0; // 최대 OR 값을 저장할 변수
    int count = 0; // 최대 OR 값을 만드는 부분집합의 개수를 셀 변수

    public int countMaxOrSubsets(int[] nums) {
        // dfs 시작 >> 현재 인덱스 0, 누적 OR 값 0부터
        dfs(nums, 0, 0);
        return count;
    }

    // dfs
    private void dfs(int[] nums, int index, int currentOr) {
        // 모든 요소를 다 확인한 경우
        if (index == nums.length) {
            // 최대 OR 값과 같은 경우 >> count 증가
            if (currentOr == maxOr) {
                count++;
            }
            // 더 큰 OR 값을 찾은 경우 >> maxOr 갱신, count 초기화
            else if (currentOr > maxOr) {
                maxOr = currentOr;
                count = 1;
            }
            return;
        }

        // 현재 인덱스의 요소를 포함한 경우 >> OR 연산 수행
        dfs(nums, index + 1, currentOr | nums[index]);

        // 현재 인덱스의 요소를 포함하지 않는 경우 >> OR 연산하지 않음
        dfs(nums, index + 1, currentOr);
    }
}

다른 사람의 코드

class Solution {
    int count = 0; // 최대 OR 값을 만드는 부분집합 개수를 저장할 변수

    public int countMaxOrSubsets(int[] nums) {
        int maxOr = 0;

        // 배열 전체에 대해 OR을 수행하여 만들 수 있는 최대 OR 값을 미리 구함
        for (int a : nums) {
            maxOr |= a;
        }

        // 백트래킹 시작 >> 현재 OR 값 0, 시작 인덱스 0
        backtrack(nums, maxOr, 0, 0);
        return count;
    }

    // 부분집합을 구성하면서 OR 결과가 최대 OR이 되면 count 증가
    void backtrack(int[] nums, int targetOr, int currOr, int index) {
        // 현재까지의 OR 결과가 최대 OR에 도달한 경우
        if (currOr == targetOr) {
            // 남은 요소들은 선택하든 안 하든 OR 값이 그대로므로
            // 가능한 부분집합의 수는 2^(남은 요소 수)
            // count += Math.pow(2, nums.length - index); 와 같지만 더 빠름
            count += 1 << (nums.length - index); 
            return;
        }

        // 인덱스부터 시작하여 모든 조합을 탐색
        for (int i = index; i < nums.length; i++) {
            // 현재 요소를 포함한 경우의 OR 값을 전달하며 다음 단계로 진행
            backtrack(nums, targetOr, currOr | nums[i], i + 1);
        }
    }
}