C++でN未満のすべての数を最大2種類の一意な数字で出力する方法

この問題では、整数Nが与えられ、N未満のすべての数のうち、最大2種類の異なる数字（ユニークな数字）のみを使用して構成される数を出力します。つまり、1つの数を作るために使える数字の種類は最大2つまでという制限があります。

問題を理解するために、具体例を見てみましょう。

入力: N = 17
出力: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

この例では、17未満の数はすべて1種類または2種類の数字で構成されているため、すべてが出力対象となります。

解法のアプローチ

この問題を解くには、2種類のユニークな数字のみで構成されるすべての数を生成します。数の生成プロセスは0から始まり、生成された数がN以上になった時点で終了します。

選択した2つの数字をiとjとすると、num*10+i と num*10+j を使って再帰的に数を生成していきます。この過程では、同じ数が複数回生成される可能性があります。そこで、setを使用して数を格納することで、重複を自動的に排除できます。

アルゴリズムの手順

1. 0から9までの数字からペア(i, j)をすべて列挙します。
2. 各ペアについて、num*10+i と num*10+j で数を再帰的に生成します。
3. 生成した数が0より大きくN未満であれば、setに追加します。
4. 最後にsetの内容を昇順で出力します。

実装例

以下のプログラムは、上記のアプローチを実装したものです。

#include <bits/stdc++.h>
using namespace std;
set<int> numbers;
void generateNumbers(int n, int num, int i, int j){
   if (num > 0 && num < n)
      numbers.insert(num);
   if (num >= n)
      return;
   if (num*10+i > num)
      generateNumbers(n, num*10+i, i, j);
   generateNumbers(n, num*10+j, i, j);
}
void printUniqueBitNumber(int n){
   for (int i = 0; i <= 9; i++)
      for (int j = i + 1; j <= 9; j++)
         generateNumbers(n, 0, i, j);
   cout<<"The numbers are generated are : ";
   while (!numbers.empty()) {
      cout<<*numbers.begin()<<" ";
      numbers.erase(numbers.begin());
   }
}
int main(){
   int n = 17;
   printUniqueBitNumber(n);
   return 0;
}

出力結果

The numbers are generated are : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16