[Leetcode] 78. Subsets - Java

문제 LINK

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

난이도 : Medium

Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.

-> Power set : 해당 집합의 모든 부분 집합을 모아둔 것이다.
Ex) {1, 2, 3}의 PowerSet {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

풀이 소스

비트연산을 통한 Subset 구현

조합(Combination) - 1~R(N)개까지 돌려서 구현이 가능하다.
- 조금 더 빠른 간단하게 풀 수 있는 법 -> 비트 연산자를 통해서 풀기.

// 조합을 돌려서
public static void combination(int [] arr, int start, int n, int r, boolean [] visited){
    if(r==0){
        List<Integer> calAns = new ArrayList<>();
        for(int i=0;i<n;i++){
        if(visited[i]){
            calAns.add(arr[i]);
        }
         ans.add(calAns);
    }

    for(int i=start;i<n;i++){

        visited[i] = true;
        combination(arr, i+1, n, r-1, visited);
        visited[i] = false;

    }
}

비트연산자를 이용해서 풀기
i 를 0 ~ 1<<n
n 이 3인 경우, 000 ~ 111(2진수) 라고 생각해볼 수 있다.

000 001 010 011 100 101 110 111

각 수에 대해서 1<<j 를 이용해서 (001 , 010 , 100 / 2 의 배수 )

&(And) 연산을 하여, 0이 아닌 j번째 nums[]를 add 해준다.

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        bitCalc(ans, nums, nums.length);
        return ans;
    }
    public static void bitCalc(List<List<Integer>> ans, int [] nums , int n){

        for(int i=0;i< 1<<n ;i++){
            List<Integer> calAns = new ArrayList<>();
            for(int j=0;j<n;j++){  
                System.out.print("I: "+i+ " J: "+j);
                if((i & 1<<j) != 0) 
                {
                    calAns.add(nums[j]);

                }
                System.out.println();
            }
           ans.add(calAns);
        }
    }    
}