Подсчет всех возможных способов выбрать N людей, по крайней мере, с X мужчинами и Y женщинами из P мужчин и Q женщин

Даны целые числа N , P , Q , X и Y , задача состоит в том, чтобы найти количество способов составить группу из N человек, состоящую как минимум из X мужчин и Y женщин из P мужчин и Q женщин , где (X + Y ≤ N, X ≤ P и Y ≤ Q) .

Примеры:

Input: P = 4, Q = 2, N = 5, X = 3, Y = 1
Output: 6
Explanation: Suppose given pool is {m1, m2, m3, m4} and {w1, w2}. Then possible combinations are:
m1 m2 m3 m4 w1
m1 m2 m3 m4 w2
m1 m2 m3 w1 w2
m1 m2 m4 w1 w2
m1 m3 m4 w1 w2
m2 m3 m4 w1 w2 

Hence the count is 6. 

Input: P = 5, Q = 2, N = 6, X = 4, Y = 1
Output: 7

Подход: эта задача основана на комбинаторике, где нам нужно выбрать не менее X мужчин из P доступных мужчин и не менее Y женщин из Q доступных женщин, так что общее количество выбранных людей равно N. Рассмотрим пример:

P = 4, Q = 2, N = 5, X = 3, Y = 1. 

In this, the possible selections are:(4 men out of 4) * (1 women out of 2) + (3 men out of 4) * (2 woman out of 2)= 4C4 * 2C1 + 4C3 * 2C2

Таким образом, для некоторых общих значений P, Q и N подход можно визуализировать как:

 

where 

Выполните шаги, указанные ниже, чтобы реализовать его:

• Начните повторять цикл от i = X до i = P.
• Проверьте, удовлетворяет ли (Ni) условию (Ni) ≥ Y и (Ni) ≤ Q . Если условие выполнено, то поступают следующим образом.
• На каждой итерации вычисляем количество возможных способов, если выбрать i мужчин и (Ni) женщин.
• Чтобы получить количество возможных способов для каждой итерации, используйте формулу
  

• Добавьте это значение для каждой итерации к общему количеству способов.
• Верните общее значение в качестве ответа.

Ниже приведена реализация подхода:

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