C++で配列要素の重複使用を許可して合計がNになる組み合わせの総数を求める方法

問題概要

この問題では、整数の配列と数値Nが与えられます。配列の要素を足し合わせてNを作る方法が全部で何通りあるかを数えるのが課題です。同じ要素の繰り返し使用は許可されており、さらに要素の並び順が異なる組み合わせはそれぞれ別の方法としてカウントします。

具体的な例を見てみましょう。

入力例

arr = {1, 3, 5}、N = 6

出力例

8

解説

N = 6 を作る8通りの方法は以下の通りです。

5+1、1+5、3+3、3+1+1+1、1+3+1+1、1+1+3+1、1+1+1+3、1+1+1+1+1+1

このように「5+1」と「1+5」のように順序だけが異なる組み合わせも、別々の方法として数える点がポイントです。

アプローチ：動的計画法（DP）

順序の異なる組み合わせをすべて区別して数える必要があるため、単純な組み合わせの列挙では対応できません。そこで有効なのが動的計画法（Dynamic Programming）です。

基本的な考え方は次の通りです。

• count[i] を「配列の要素の和で i を作る方法の総数」と定義する。
• 初期条件として count[0] = 1 とする（何も加算しない状態、すなわち合計0を作る方法は1通り）。
• i を 1 から N まで順番に計算し、各配列要素 array[j] について、i ≥ array[j] であれば count[i] += count[i − array[j]] と更新する。
• 最終的な答えは count[N] となる。

この方法の計算量は O(N × 配列のサイズ) であり、効率的に答えを求められます。

C++での実装例

#include <iostream>
#include <cstring>
using namespace std;
int arraySumWays(int array[], int size, int N){
    int count[N + 1];
    memset(count, 0, sizeof(count));
    count[0] = 1;
    for (int i = 1; i <= N; i++)
        for (int j = 0; j < size; j++)
            if (i >= array[j])
                count[i] += count[i - array[j]];
    return count[N];
}
int main() {
    int array[] = {1, 5, 6};
    int size = sizeof(array) / sizeof(array[0]);
    int N = 7;
    cout<<"Total number of ways inwhich "<<N<<" can be generated using sum of elements of array is "
        <<arraySumWays(array, size, N);
    return 0;
}

出力結果

Total number of ways inwhich 7 can be generated using sum of elements of array is 6

このプログラムでは、配列 {1, 5, 6} の要素を使って 7 を作る方法が 6 通りあることが確認できます。