1223. How Many Ways to Pair Everybody Up

There are n people, with n even, and m forbidden pairs. Report how many ways there are to split everybody into pairs so that no forbidden pair is used. Two splits are the same if they use the same set of pairs; the order of the pairs and the order within a pair do not matter.

4 people, nothing forbidden -> 3 12|34, 13|24, 14|23 4 people, 1-2 forbidden -> 2 13|24, 14|23 20 people, nothing forbidden -> 654729075

## What most people try first

Enumerate the n! orderings of the people and read each one as the pairs (1st, 2nd), (3rd, 4th), .... Every valid split appears, and it appears many times: once per way of swapping the two members inside each pair, 2^(n/2) ways, times once per way of ordering the pairs, (n/2)! ways. At n = 20 that is 2^10 * 10! = 3715891200 copies of each split, out of 20! orderings. The method is correct after dividing and it is useless as a program.

## The symmetry break

Always pair the LOWEST unmatched person next.

That is the whole fix. A split is a set of pairs with no order, so choosing who to deal with first in any other way reaches the same split once per ordering of its pairs. Fixing the choice to the lowest unmatched person removes all of that: at every step there is exactly one person who must be dealt with, and the only freedom left is who to pair them with. So each split is reached exactly once, and the (n/2)! orderings of the pairs and the 2^(n/2) swaps inside pairs both disappear, because the lowest person of a pair is always the one chosen and the other is always the partner.

## The canonical state

After the symmetry break the search still revisits the same situations by different routes: pairing 1 with 2 and then 3 with 4 leaves the same people unmatched as pairing 1 with 2 and then 3 with 4 by any other path to it. What the number of completions depends on is only WHO IS STILL UNMATCHED, which is a subset of the people.

So memoise on that subset, held as n bits of one integer. There are 2^n subsets, each computed once at a cost of O(n), giving O(2^n * n) against O(n!). At n = 20 that is about twenty million operations instead of 2.4 * 10^18 orderings.

Only subsets of even size are ever reached, so half the table is never touched; allocating all of it is simpler than indexing around the gap and costs nothing worth saving.

## Why the two ideas are both needed

Without the symmetry break, memoising on the unmatched set is still correct and the recursion loops over every unmatched person as the one to pair next, which does n/2 times too much work per state and, more importantly, makes the correctness argument harder: you would be counting ordered sequences of pairs and dividing at the end. Without the memo, the symmetry break alone gives a correct search whose cost is the number of splits, which at n = 20 is 654 million. Together they give a program that answers instantly, and each one is doing a different job: the break makes each answer reachable once, the memo makes each situation computed once.

## Overflow

With nothing forbidden the answer is the double factorial (n-1)!!, that is 1 * 3 * 5 * ... * (n-1), because person 1 has n-1 choices of partner and then the problem repeats on n-2 people. At n = 20 that is 19!! = 654729075, which FITS in a signed 32-bit integer, since INT_MAX = 2147483647 is more than three times larger. So a 32-bit counter is correct for every input the constraints allow. Pushing to n = 22 would give 21!! = 13749310575 and genuinely overflow, which is why the limit is 20.

## The settled boundaries

Two people with nothing forbidden have one split; two people forbidden to each other have none, so the answer is 0 and not the word none. A person forbidden to pair with everybody makes the answer 0. All three are tested.

## Cost

O(2^n * n) time and O(2^n) memory.

Constraints - `2 ≤ n ≤ 20` and `n` is even - `0 ≤ m ≤ n * (n - 1) / 2` - `1 ≤ u, v ≤ n` and `u != v` - no pair is repeated - the answer is at most `19!! = 654729075`, which fits in a signed 32-bit integer