質問リンク

問題の説明

に答える

コード#コード#

from itertools import combinations


def solution(relation):
    candidates = set()
    cols = len(relation[0])
    for i in range(1, cols + 1):
        for combi in combinations(range(cols), i):
            if possible(relation, candidates, combi):
                candidates.add(combi)
    return len(candidates)


def possible(relation, candidates, combi):
    # 최소성
    for i in range(1, len(combi) + 1):
        for combi2 in combinations(combi, i):
            if combi2 in candidates:
                return False
    # 유일성
    unique = set()
    for line in relation:
        curr = []
        for i in combi:
            curr.append(line[i])
        if tuple(curr) in unique:
            return False
        unique.add(tuple(curr))
    return True