import java.util.*;

class Solution {
    public int solution(String[][] relation) {
        int maxRow = relation.length;
        int maxCol = relation[0].length;
        
        // 정답 후보키들을 저장할 리스트 (비트마스크 형태로 저장)
        List<Integer> candidateKeys = new ArrayList<>();

        // 1. 모든 컬럼 조합 탐색 (1부터 2^maxCol - 1까지)
        // ex) 컬럼이 4개면 1(0001)부터 15(1111)까지
        for (int set = 1; set < (1 << maxCol); set++) {
            
            // 2. 최소성 검사
            // 현재 조합(set)에 기존에 찾은 후보키가 이미 포함되어 있다면 군더더기이므로 패스
            if (!isMinimal(set, candidateKeys)) {
                continue;
            }

            // 3. 유일성 검사
            if (isUnique(set, relation, maxRow, maxCol)) {
                // 유일성과 최소성을 모두 만족하면 후보키로 등록
                candidateKeys.add(set);
            }
        }

        // 찾아낸 후보키의 개수 반환
        return candidateKeys.size();
    }

    // 최소성 검사 메서드
    private boolean isMinimal(int set, List<Integer> candidateKeys) {
        for (int key : candidateKeys) {
            // 비트 AND 연산을 통해 기존 키(key)가 현재 조합(set)의 부분집합인지 확인
            if ((set & key) == key) {
                return false; // 포함되어 있다면 최소성 위반!
            }
        }
        return true;
    }

    // 유일성 검사 메서드
    private boolean isUnique(int set, String[][] relation, int maxRow, int maxCol) {
        Set<String> tupleSet = new HashSet<>();
        
        for (int r = 0; r < maxRow; r++) {
            StringBuilder sb = new StringBuilder();
            
            for (int c = 0; c < maxCol; c++) {
                // 비트 연산으로 c번째 컬럼이 선택되었는지 확인
                if ((set & (1 << c)) != 0) {
                    sb.append(relation[r][c]).append(","); // 구분자(,) 추가 필수!
                }
            }
            tupleSet.add(sb.toString());
        }
        
        // 만들어진 튜플의 개수가 전체 로우 개수와 같다면 중복이 없다는 뜻 (유일성 만족)
        return tupleSet.size() == maxRow;
    }
}