후보키 자바스크립트

function solution(relation) {
    let answer = 0;
    let row = relation.length;
    let col = relation[0].length;
    let mask = [];
    
    for(let i = 1; i < (1 << col); i++) {
        let set = new Set();
        for(let j = 0; j < row; j++) {
            let key = '';
            for(let k = 0; k < col; k++) {
                if((i & 1 << k)) key += relation[j][k];
              }
            set.add(key);
        }
        if(set.size == row && notDuplicate(mask,i)) answer++
    }
    return answer;
}

function notDuplicate(arr,num) {
    for(let i = 0; i < arr.length; i++) {
        if((arr[i] & num) == arr[i]) return false;
    }
    arr.push(num);
    return true;
}

비트연산자, 부분집합, 중복검사, set 등의 복잡한 지식이 많이 들어간 풀이이다.

먼저 column이 n인 부분집합의 개수는 2^n인데 여기서 공집합을 제외하면 2^n -1개가 나온다.

그래서 총 2^n -1만큼 반복문을 돌려 부분집합의 경우의 수를 찾아내겠다는 의미로 반복문의 시작을
for(let i =1; i < (1 << col); i++))로 한다.

여기서 1 << col의 << 는 비트 연산자로 1을 왼쪽으로 col만큼 민 후 10진수로 표현하면 2^n이 된다.

2^n -1만큼 2차원 배열을 반복하기 위해 j,k 반복문을 추가한다.
k 반복문에서 (i & (1 << k)) 가 0이 아닐 경우임을 추가해야지 올바르게 모든 경우의 수들을 set에 넣을 수 있다.
(배열의 모든 요소를 2진수로 생각하여 풀이. 부분조합에 포함할 경우 1 아닐경우 0)

set에는 중복된 값이 저장되지 않으므로 후보키로 가능하려면 set의 길이와 row가 같아야하며 notDuplicate 함수로
최소성을 검사할 수 있다.

k 반복문 : if((i & 1 << k))
희소성 검사 : for(let i = 0; i < arr.length; i++) {
if((arr[i] & num) == arr[i]) return false;
}
두 공식은 외워두면 요긴하게 사용할 수 있을 것 같다.