Сочетаниями из n элементов по k называются соединения, которые можно образовать из n элементов, собирая в каждое соединение k элементов; при этом соединения отличаются друг от друга только самими элементами (различие порядка их расположения во внимание не принимается).
Например, из 3 элементов (a,b,c)(a,b,c) по 2 можно образовать следующие сочетания: ab,ac,bc.
Число всех возможных сочетаний, которые можно образовать из n элементов по k, обозначается символом
и вычисляется по формуле:
Есть два способа найти количество сочетаний
1. Найдем n!, k!, (n – k)! и по формуле приведенной сверху посчитаем количество, но из – за возможного переполнения этот способ можно использовать при n <= 12.
2. С помощью динамического программирования.
ДП будет выглядеть как треугольник Паскаля, на вершине и по краям стоят единицы, а каждое число равно сумме двух расположенных над ним чисел.
Функция считающая количество сочетаний с помощью динамическое программирование за О(n ^2 ):
int C(int n, int k)
{
vector<vector<int> > dp(n + 1, vector<int>(n + 1, 1)); // Создаем массив dp размером (n + 1, n + 1)
for (int i = 0; i <= n; i++) // Заполняем i-ю строку массива
{
for (int j = 1; j < i; j++)
{
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; //пересчет (i;j) позиции через (i - 1; j - 1) и (i - 1; j)
}
}
return dp[n][k]; //вернем значение
}