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

Даны целые числа N , P и Q. Задача состоит в том, чтобы найти количество способов составить группу из N человек , в которой будет хотя бы 4 мальчика и 1 девочка из P мальчиков и Q девочек .

Примеры:

Input:  P = 5, Q = 2, N = 5
Output: 10
Explanation:  Suppose given pool is {m1, m2, m3, m4, m5} and {w1, w2}. Then possible combinations are: 

m1 m2 m3 m4 w1
m2 m3 m4 m5 w1
m1 m3 m4 m5 w1
m1 m2 m4 m5 w1
m1 m2 m3 m5 w1
m1 m2 m3 m4 w2
m2 m3 m4 m5 w2
m1 m3 m4 m5 w2
m1 m2 m4 m5 w2
m1 m2 m3 m5 w2

Hence the count is 10.

Input:  P = 5, Q = 2, N = 6
Output: 7

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

 P = 5, Q = 2, N = 6 
In this, the possible selections are:
(4 boys out of 5) * (2 girls out of 2) + (5 boys out of 5) * (1 girl out of 2)
= 5C4 * 2C2 + 5C5 * 2C1

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

куда

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

• Начните повторять цикл от i = 4 до i = P .
• На каждой итерации вычислить количество возможных способов, если мы выберем i мальчиков и (Ni) девочек, используя комбинацию
  
• Добавьте возможное значение для каждой итерации как общее количество способов.
• Верните общее количество рассчитанных способов в конце.

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

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