algorithm - 長さ n のすべてのバイナリ文字列を再帰的に生成する最良の方法は何ですか?

Question

長さ のすべてのバイナリ文字列を生成する優れた (実装が簡単、直感的など)再帰的な方法を探していnます1 <= n <= 35。

擬似コード アルゴリズムのアイデアをいただければ幸いです (言語固有のトリックはありません)。

LE: わかりました。上限を設定しすぎました。1私の意図は、 からまでのカウンターのバイナリ表現を使用するソリューションを避けることでした1 << n。

Answer 1

C++ での再帰の例を次に示します。

vector<string> answer;

void getStrings( string s, int digitsLeft )
{
   if( digitsLeft == 0 ) // the length of string is n
      answer.push_back( s );
   else
   {
      getStrings( s + "0", digitsLeft - 1 );
      getStrings( s + "1", digitsLeft - 1 );
   }
}

getStrings( "", n ); // initial call

Answer 2

Divide et Impera パラダイムによれば、長さ n のすべてのバイナリ文字列を生成する問題は、2 つのサブ問題に分割できます。長さ n-1 のすべてのバイナリ文字列を 0 の前に出力する問題と、n-1 のすべてのバイナリ文字列を出力する問題です。長さ n-1 の前に 1 があります。したがって、次の疑似コードで問題を解決できます。

generateBinary(length, string)

if(length > 0)
    generateBinary(length-1, string + "0")
    generateBinary(length-1, string + "1")
else
    print(string)