C++でn桁の厳密に増加する数をすべて出力する方法

この問題では、数値Nが与えられ、最上位桁（MSB）から最下位桁（LSB）にかけて各桁が厳密に増加しているすべてのn桁の数を出力することが求められます。つまり、左側の桁は必ずその右隣の桁より小さくなければなりません。

問題例

入力： n = 2

出力：

01 02 03 04 05 06 07 08 09 12 13 14 15 16 17 18 19 23 24 25 26 27 28 
29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89.

解説： 出力結果を見ると、どの数も左側の桁が右側の桁よりも小さくなっていることが確認できます。

解法のアプローチ

この問題を解くには、最上位桁（左側）から順に0〜9の数字を一つずつ選び、条件に従って残りの桁を生成していきます。現在の位置で選んだ桁をiとすると、次の位置には「i+1から9」までの数字のみを配置できます。この処理を再帰的に繰り返すことで、条件を満たすすべての組み合わせを効率よく列挙できます。

なお、n桁の厳密に増加する数の総数は、0〜9の10個の数字からn個を選ぶ組み合わせの数 C(10, n) と一致します。そのため、探索範囲が限定され、非常に効率的なアルゴリズムになります。

C++での実装例

#include <iostream>
using namespace std;
void printIncresingNumbers(int start, string out, int n) {
    if (n == 0){
        cout<<out<<" ";
        return;
    }
    for (int i = start; i <= 9; i++){
        string str = out + to_string(i);
        printIncresingNumbers(i + 1, str, n - 1);
    }
}
int main() {
    int n = 3;
    cout<<"All "<<n<<" digit strictly increasing numbers are :\n";
    printIncresingNumbers(0, "", n);
    return 0;
}

コードのポイント

• 関数printIncresingNumbersは、「次に選べる最小の数字（start）」「現在構築中の数を表す文字列（out）」「残りの桁数（n）」を受け取ります。
• 残りの桁数nが0になった時点で、完成した数を出力して再帰を終了します。
• それ以外の場合は、startから9までの各数字iについて文字列に追加し、開始値をi+1として再帰呼び出しを行います。これにより、常に左の桁が右の桁より小さいという条件が自動的に保証されます。

実行結果

All 3 digit strictly increasing numbers are −
012 013 014 015 016 017 018 019 023 024 025 026 027 028 029 034 035 036 
037 038 039 045 046 047 048 049 056 057 058 059 067 068 069 078 079 089 
123 124 125 126 127 128 129 134 135 136 137 138 139 145 146 147 148 149 
156 157 158 159 167 168 169 178 179 189 234 235 236 237 238 239 245 246 
247 248 249 256 257 258 259 267 268 269 278 279 289 345 346 347 348 349 
356 357 358 359 367 368 369 378 379 389 456 457 458 459 467 468 469 478 
479 489 567 568 569 578 579 589 678 679 689 789

このように、シンプルな再帰処理を用いるだけで、桁が厳密に増加するすべてのn桁の数を漏れなく重複なく出力できます。組み合わせ爆発を避けるため、探索候補が毎回絞り込まれる点が本手法の大きな利点です。