Partition into pairs

Write codeHard35 min

Your task

You have n people (n even) and an n x n symmetric boolean matrix compatible where compatible[i][j] is 1 if person i and j can be paired. Count the number of ways to partition ALL people into n/2 compatible pairs (each person in exactly one pair). Two partitions are the same if they use the same set of pairs. Return the count. 2 <= n <= 14, n even, compatible[i][i]=0.

Examples

count_perfect_matchings(compatible: list[list[int]]) -> int
Example 1
Inputcount_perfect_matchings([[0, 1], [1, 0]])
Output1