Число сочетаний можно найти используя рекурсию и, соответственно, рекуррентное соотношение. Код получается вот такой:
def C(n, k):
if k == n or k == 0:
return 1
if k != 1:
return C(n-1, k) + C(n-1, k-1)
else:
return n
print(C(int(input()), int(input())))
Но я знаю, что рекурсия штука не быстрая и не всегда надежная. Есть ли другие алгоритмы и на сколько они быстрые?
n! / (k! (n - k)!)
. Факториал реализован в функцииmath.factorial
. Ваш алгоритм не оптимален, но не потому, то рекурсия медленная, а потому, что результаты не кешируются.@functools.lru_cache(None)
значительно ускорит программу.