combination

[C++] 조합 (Combination) 구할 수 있는 알고리즘

개념n개의 값 중에서 r 개의 숫자의 순서를 고려하지 않고 나열한 경우의 수, 순열은 반대로 고려한다. 예시) [1,2] 와 [2,1] 이 있을 때 동일하게 여긴다는 의미계산식으로는 nCr 이라고 표현한다.nCr= nPr / r!= n! / ((n-r)! * r!)예시로 서로 다른 3개의 숫자(1,2,3) 중 중복되지 않으면서 순서와 관계 없이 2개를 뽑는다고 가정해보자3C2= 3! / 1! * 2!= 3! / 2!= (3x2x1) / (2x1)= 3로 총 3개의 경우의 수가 나오게 된다 (1,2 / 1,3 / 2,3) 조합의 점화식 n-1Cr-1 + n-1Crn-1Cr-1 : 어떤 특정한 원소를 포함시키고 뽑았을 때n-1Cr : 어떤 특정한 원소를 포함시키지 않고 뽑았을 때예시){1,2,3} 에서 3C..