C++에서 요소가 양의 정수이고 합계가 K인 크기가 N인 배열의 수

<시간/>

두 개의 숫자 n과 k가 주어집니다. 합이 k인 n개의 숫자를 사용하여 구성할 수 있는 배열의 수를 찾아야 합니다.

크기가 N이고 합이 K인 배열의 수는 $\dbinom{k - 1}{n - 1}$입니다.

이것은 합이 k인 n개의 요소를 사용하여 형성할 수 있는 숫자 배열을 찾는 간단한 공식입니다. 예를 들어 보겠습니다.

입력

n = 1
k = 2

출력

구성할 수 있는 유일한 배열은 [2]

입니다.

입력

n = 2
k = 4

출력

구성할 수 있는 배열은 [1, 3], [2, 2], [3, 1]입니다.

알고리즘

숫자 n과 k를 초기화합니다.
숫자의 계승을 계산하는 함수를 작성하십시오.
이제 위와 같이 이항을 계산하는 주요 함수를 작성합니다.
답을 반환합니다.

구현

다음은 위의 알고리즘을 C++로 구현한 것입니다.

#include <bits/stdc++.h>
using namespace std;
int factorial(int n) {
   int result = 1;
   for (int i = 2; i <= n; i++) {
      result *= i;
   }
   return result;
}
int getNumberOfArraysCount(int n, int k) {
   return factorial(n) / (factorial(k) * factorial(n - k));
}
int main() {
   int N = 5, K = 8;
   cout << getNumberOfArraysCount(K - 1, N - 1) << endl;
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.