C++で指定した合計点を作る1・2・3のポイント組み合わせをすべて出力する方法

この記事では、与えられた合計得点 n に対して、バスケットボールの得点である 1、2、3 の組み合わせの中から、合計がちょうど n になるすべてのパターンを出力する方法を解説します。

問題の概要

まず、具体例を見ながら問題を理解しましょう。

入力: 4
出力:
1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1

このように、合計が4になる1・2・3の並び順を含むすべての組み合わせ（順列）が出力されます。順序が異なるものは別の組み合わせとして扱う点に注意してください。

解決のアプローチ：再帰を活用

この問題は再帰（recursion）を使うことでシンプルに解けます。基本的な考え方は以下の通りです。

• 現在の残り合計 n に対して、得点 s（1〜3）を1つ選んで固定します。
• 残りの値 n - s に対して同じ処理を再帰的に繰り返します。
• n が 0 になった時点で、それまでに選んだ得点の並びが合計 n を満たす組み合わせなので、これを出力します。

この手法により、すべての有効な組み合わせを網羅的に探索できます。

C++での実装例

以下が実際のコードです。

#define MAX_POINT 3
#define ARR_SIZE 100
#include <bits/stdc++.h>
using namespace std;

void printScore(int arr[], int arr_size) {
    int i;
    for (i = 0; i < arr_size; i++)
        cout<<arr[i]<<" ";
    cout<<endl;
}

void printScoreCombination(int n, int i) {
    static int arr[ARR_SIZE];
    if (n == 0) {
        printScore(arr, i);
    }
    else if(n > 0) {
        int k;
        for (k = 1; k <= MAX_POINT; k++){
            arr[i]= k;
            printScoreCombination(n-k, i+1);
        }
    }
}

int main() {
    int n = 4;
    cout<<"Different compositions formed by 1, 2 and 3 of "<<n<<" are\n";
    printScoreCombination(n, 0);
    return 0;
}

コードのポイント

• MAX_POINT：使用できる最大の得点（ここでは3）を定義しています。
• arr：現在探索中の組み合わせを一時的に保持する静的配列です。
• printScoreCombination(n, i)：残り合計 n と、配列の書き込み位置 i を引数に取り、再帰的に組み合わせを生成します。
• n が 0 になったタイミングで printScore() を呼び出し、完成した組み合わせを出力します。

実行結果

Different compositions formed by 1, 2 and 3 of 4 are
1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1

このように、合計が4になる7通りの組み合わせがすべて出力されました。再帰による深さ優先探索の考え方を理解すれば、同様の「組み合わせ列挙」系の問題にも応用できます。