【C++】合計がKとなるサイズNの配列（要素は正の整数）の個数を求める方法

問題の概要

2つの整数 n と k が与えられたとき、「n 個の正の整数から構成され、その総和が k になる配列」が何通り作れるかを求めます。

この問題の答えは、次の二項係数で表されます。

$\dbinom{k - 1}{n - 1}$

つまり「k − 1 個の中から n − 1 個を選ぶ組み合わせ」の総数が、条件を満たす配列の個数になります。これは「重複組合せ」として知られる有名な公式です。

なぜこの公式が成り立つのか

配列の各要素は 1 以上であるため、各要素から 1 を引いて考えると、「0 以上の整数 n 個の和が k − n になる場合の数」に帰着できます。重複組合せの公式より、これは $\dbinom{(k-n)+n-1}{n-1}=\dbinom{k-1}{n-1}$ となり、上記の式と一致します。

入出力例

例1

入力

n = 1
k = 2

出力

1

条件を満たす配列は [2] のみです。

例2

入力

n = 2
k = 4

出力

3

作れる配列は [1, 3]、[2, 2]、[3, 1] の 3 通りです。

アルゴリズム

• 整数 n と k を初期化します。
• ある数の階乗を計算する関数を作成します。
• 上記の二項係数を計算する本体の関数を実装します。
• 結果を返します。

C++での実装

以下は、上記のアルゴリズムを 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;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

35

N = 5、K = 8 の場合、$\dbinom{7}{4}=35$ となり、理論値と一致します。

まとめ

「総和が K になるサイズ N の正の整数配列」の個数は、二項係数 $\dbinom{K-1}{N-1}$ で直接求められます。階乗を使ったシンプルな実装で十分ですが、N や K が大きくなると int 型ではオーバーフローする恐れがあるため、long long 型の利用や、パスカルの三角形による漸化式での計算、さらに大きな数に対しては mod 逆元を使った剰余計算を検討するとよいでしょう。