C++で桁の合計が指定した値と一致するすべてのn桁の数を出力する方法

この問題では、2つの整数 n と sum が与えられます。求めるのは、各桁の数字の合計が sum と一致するすべての n 桁の数です。なお、先頭に 0 が付く数(例：014 など)は n 桁の数として扱いません。

問題の例

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

入力: n = 2 , sum = 5
出力: 14 23 32 41 50
説明: 出力されたすべての数は、各桁の合計が 5 になっています。

解決のアプローチ

この問題を解くには、条件を満たす n 桁の数をすべて列挙する必要があります。そこで再帰的な手法を用います。まず最上位の桁に 1〜9 の値を順に固定し(先頭の 0 を除外するため)、残りの桁については 0〜9 の値を再帰的に割り当てていきます。

各ステップでは、残りの合計から現在の桁に設定した値を差し引きます。そして、すべての桁を埋め終えた時点で残りの合計がちょうど 0 になっていれば、その数は条件を満たしていることになります。もし途中で合計が負になった場合は、その経路は打ち切ります。

C++での実装例

上記の考え方を実装したプログラムは以下の通りです。

#include <iostream>
using namespace std;

// 条件を満たす数を再帰的に生成する関数
void PrintNumberWithDigitSum(int n, int sum, char* out, int index) {
    if (index > n || sum < 0)
        return;
    if (index == n) {
        if (sum == 0) {
            out[index] = '\0';
            cout << out << " ";
        }
        return;
    }
    for (int i = 0; i <= 9; i++) {
        out[index] = i + '0';
        PrintNumberWithDigitSum(n, sum - i, out, index + 1);
    }
}

// 最上位の桁を 1〜9 で固定して探索を開始する関数
void numberWithSum(int n, int sum) {
    char out[n + 1];
    for (int i = 1; i <= 9; i++) {
        out[0] = i + '0';
        PrintNumberWithDigitSum(n, sum - i, out, 1);
    }
}

int main() {
    int n = 3, sum = 6;
    cout << "All " << n << " digit numbers with sum " << sum << " are :\n";
    numberWithSum(n, sum);
    return 0;
}

実行結果

上記のプログラムを n = 3、sum = 6 として実行すると、次のような出力が得られます。

All 3 digit numbers with sum 6 are −
105 114 123 132 141 150 204 213 222 231 240 303 312 321 330 402 411 420 501 510 600

出力されたすべての 3 桁の数について、各桁の合計が 6 になっていることが確認できます。

まとめ

このように、再帰を用いて各桁の値を順に決定していくことで、桁の合計が指定した値と一致する n 桁の数を効率的にすべて列挙できます。最上位の桁だけ 1 から始めることで、先頭に 0 が付く数を自然に除外できる点もポイントです。