C++で指定した合計値となるすべての組み合わせを求める方法

正の整数 n が与えられたとき、その数の合計となるすべての正の数の組み合わせを求めることを考えます。ここで必要なのは「組み合わせ」であり、「順列」ではない点に注意してください。例えば n = 4 の場合、答えは [1, 1, 1, 1]、[1, 1, 2]、[1, 3]、[2, 2]、[4] の5通りになります。

アプローチ：再帰を利用した解法

この問題は再帰（リカージョン）を使うことで効率的に解くことができます。組み合わせを一時的に格納するための配列を用意し、再帰呼び出しを通じてその配列を順に埋めていきます。

重複する順列を避けるため、各組み合わせの要素は必ず昇順に格納されるようにします。具体的には、「次の位置に配置できる数値は、直前に配置した数値以上」という制約を設けることで実現します。

アルゴリズムの流れ

1. 残りの合計値（decrement）が 0 未満になった場合は、その探索経路を打ち切ります。
2. 残りの合計値がちょうど 0 になった場合、配列に格納されている値の並びが1つの組み合わせとして成立しているため、それを出力します。
3. それ以外の場合は、直前の要素以上の数値 k を順に試し、配列に格納したうえで再帰呼び出しを行います。

サンプルコード（C++）

#include<iostream>
using namespace std;
void getCombination(int arr[], int index, int num, int decrement) {
    if (decrement < 0)
        return;
    if (decrement == 0){
        for (int i = 0; i < index; i++)
            cout << arr[i] << " ";
            cout << endl;
            return;
    }
    int prev;
    if(index == 0)
    prev = 1;
    else
        prev = arr[index-1];
    for (int k = prev; k <= num ; k++) {
        arr[index] = k;
        getCombination(arr, index + 1, num, decrement - k);
    }
}
void findCombinations(int n) {
    int arr[n];
    getCombination(arr, 0, n, n);
}
int main() {
    int n = 4;
    findCombinations(n);
}

実行結果

1 1 1 1
1 1 2
1 3
2 2
4

コードの解説

getCombination 関数は4つの引数を受け取ります。arr は現在構築中の組み合わせを保持する配列、index は次に値を格納する位置、num は目標となる合計値、decrement はまだ埋めるべき残りの合計値です。

index が 0 のとき（最初の要素）は 1 から探索を開始し、それ以降は直前の要素 arr[index-1] 以上の値のみを試します。この昇順の制約により、[1, 3] と [3, 1] のような順列の重複が排除され、組み合わせだけが出力されます。

decrement が 0 になった時点で、配列に格納された値の合計がちょうど n と一致しているため、その内容を出力して再帰を終了します。負になった場合は、合計が n を超えてしまったことを意味するため、その経路は即座に放棄されます。

まとめ

このように、再帰と「直前の要素以上」という単純な制約を組み合わせるだけで、指定した数の合計となるすべての組み合わせを重複なく列挙できます。計算量は組み合わせの総数に依存しますが、n が小規模な範囲であれば非常にシンプルで実用的な手法です。