Количество способов, которыми N элементов могут образовывать два разных множества, содержащих по N/2 элементов в каждом

Учитывая число N , представляющее количество элементов и равное 2K , задача состоит в том, чтобы найти количество способов, которыми эти элементы могут быть сформированы из 2 наборов, содержащих K элементов каждый.

Примеры:

Input: N = 4
Output: 3
Explanation: The 3 sets consisting of 2 (= N/2) elements are:
             [1, 2], [3, 4]
             [1, 3], [2, 4]
             [1, 4], [2, 3]           

Input: N = 20
Output: 12164510040883200

Подход: Следует отметить, что концепция комбинаций должна применяться для выбора элементов для каждого набора.
Известно, что количество способов выбрать r вещей из n вещей равно:

^{nC_{r = n!/(n-r)!*r!}} 
 

Теперь приведенную выше формулу можно изменить для решения данной задачи:

• Здесь необходимо выбрать N/2 элементов из N элементов, чтобы сформировать каждый набор. Следовательно, r = N/2 .
• Следует отметить, что один и тот же элемент не может одновременно присутствовать в двух наборах. Итак, формула ⁿ C _r надо разделить на 2.
• Кроме того, элементы, присутствующие в каждом наборе, могут располагаться в (N/2-1)! способы. Поскольку наборов два, формула будет умножаться на этот коэффициент дважды.

Полученная модифицированная формула имеет вид:

Number of ways = ((N! / (N – r)!*r!) / 2) * (N / 2 – 1)!*(N / 2 – 1)! where r = N / 2

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)