[LeetCode] 78. Subsets - 비트마스킹(BitMask) JAVA

https://leetcode.com/problems/subsets/description/

코드설명

비트마스킹(BitMask) 을 활용합니다.

 

물론, 이 문제에서 재귀를 활용해도 됩니다만, BitMask의 경우 부분집합 구현에 유명한 방식이기에 BitMask 방식을 사용합니다.

모든 칸을 1111 의 집합이 존재할경우 가능한 부분집합의 개수는 2^4 입니다. 즉, 결국 BitMask에서 -1 씩 뺴면서 0으로 만드는 경우를 모두 진행하면, 모든 경우가 나온다는 의미입니다.

 

결국 1111의 값을 0으로 만들면서 15, 14, 13, 12, 11, ... 0 까지 움직이며, 각 숫자마다 비트마스킹으로 1의 위치에 따른 값을 ret list에 넣어주면, 해당 집합의 모든 부분집합을 구할 수 있습니다.

코드

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int N = nums.length;
        int bitmask = (1 << N) - 1;//111
        List<List<Integer>> answer = new ArrayList<>();
        answer.add(new ArrayList<>());
        for(int subset = bitmask; subset > 0; subset = ((subset - 1) & bitmask)){
            ArrayList<Integer> ret = new ArrayList<Integer>();
            int newsubset = subset; //처음에 subset을 바로 사용했음. 그럴경우 timeout.
            int k = 0;
            while(newsubset > 0){
                if( (newsubset & 1) > 0){
                    ret.add(nums[N - 1 - k]);
                }
                k++;
                newsubset >>= 1;
            }
            Collections.reverse(ret);
            answer.add(ret);
        }
        return answer;
    }
}