[JAVA] bit 연산을 활용한 부분집합 만들기

오늘 강의를 듣다가 생각도 못한 부분을 배웠다.

바로 부분집합을 구하는 것을 bit 연산을 사용할 수 있다는 것이다.

만약 부분집합을 구해라라는 문제가 있었다면,

나는 아마 백트레킹(?)으로 풀지 않았을까 생각했는데 비트연산 신선했다.

 

사실 그동안 비트 연산에 대해 잘 몰랐는데 이번 기회에 좀 알아야겠다.

 

import java.util.*;
import java.io.*;

public class 부분잡헙만들기_bit이용 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
//		StringTokenizer st = new StringTokenizer(str);
		String [] set = str.split(" ");
		int set_size = set.length;
		
		for(int i=0;i<(1<<set_size);i++) {
			for(int j=0; j<set_size;j++) {
				if ((i & (1<<j)) > 0) {
					System.out.print(set[j]+" ");
				}
			}
			System.out.println();
		}
		
	}

}