[알고리즘] 비트마스킹 - 순열, 조합, 부분집합

1. 부분집합 - 비트마스킹

int[] arr = {1, 2, 3, 4, 5};


int length = arr.length; 		//2의 5승
System.out.println(1<<length); 		//32

for (int i=0; i<(1<<length); i++) {		// 부분집합의 개수
    for (int j=0; j<length; j++) {
        if ((i & (1<<j)) != 0) {		// 존재한다
            // TODO~~
        }
    }
}

 

2. 순열 - 비트마스킹

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

public class Main {

    static int[] arr = {1, 2, 3, 4, 5};
    static int[] tgt = new int[3];

    public static void main(String[] args) throws Exception {
        System.out.println("test:"+(18 & (1<<3)));  //0

        perm(0, 0);
    }

	// 순열 - 비트마스킹
    static void perm(int idx, int flag) {
        if (idx == 3) {
            System.out.println(Arrays.toString(tgt));
            return;
        }
        for (int i=0; i<arr.length; i++) {
            if ((flag & (1<<i)) != 0) continue;
            tgt[idx] = arr[i];
            perm(idx+1, flag|1<<i);
        }
    }
}