Cプログラムで配列またはループを使用せずに{1,2,3、…n}のすべてのサブセットを出力する

正の整数nが与えられた場合、配列やループを使用せずに、{1、2、3、4、…n}のセットのすべてのサブセットを出力する必要があります。

任意の数、たとえば3を指定したように、セット{1、2、3}内のすべてのサブセットを出力する必要があります。これは{1 2 3}、{1 2}、{2 3}、{1 3}、 {1}、{2}、{3}{}。

ただし、ループや配列を使用せずにこれを行う必要があります。したがって、配列やループを使用せずにこのタイプの問題を解決するための可能な方法は、再帰のみです。

例

入力：3出力：{1 2 3} {1 2} {1 3} {1} {2 3} {2} {3} {}説明：セットは{123}になります。サブセットを見つける入力：4出力：{1 2 3 4} {1 2 3} {1 2 4} {1 2} {1 3 4} {1 3} {1 4} {1} {2 3 4} {2 3 } {2 4} {2} {3 4} {3} {4} {} 

特定の問題を解決するために使用するアプローチ −

• num =2 ^n-1から0まで。
• n個のビットを持つnumのバイナリ表現を検討してください。
• 1を表す左端のビットから開始し、2番目のビットは2を表し、以下同様にnを表すn番目のビットまで続きます。
• ビットが設定されている場合は、ビットに対応する番号を出力します。
• numのすべての値に対して、0になるまで上記の手順を実行します。

簡単な例を使用して、説明されているアプローチがどのように機能するかを詳しく理解しましょう-

入力n=3と仮定すると、問題はnum =2 ^ 3-1=7から始まります

• 7のバイナリ表現⇒

• 対応するサブセット⇒

numから1を引く; num =6

• 6のバイナリ表現⇒

• 対応するサブセット⇒

numから1を引く; num =5

• 5のバイナリ表現⇒

• 対応するサブセット⇒

numから1を引く; num =4

• 4のバイナリ表現⇒

• 対応するサブセット⇒

同様に、num =0になるまで繰り返し、すべてのサブセットを出力します。

アルゴリズム

ステップ1を開始→関数内intsubset（int bitn、int num、int num_of_bits）If bitn> =0 If（num＆（1 < =0）Print "{" Call function subset（num_of_bits-1、num、num_of_bits）Print "}" Call function printSubSets（ num_of_bits、num-1）Else Return 0Return1ステップ3→Infunctionint main（）int n =4を宣言して初期化しますfucntionprintSubSets（n、（int）（pow（2、n））-1）Stop> 
例
 
 #include  #include  //この関数は、num.intサブセットのバイナリ//表現に対応する//サブセットを再帰的に出力します（int bitn、int num、int num_of_bits）{ if（bitn> =0）{//指定されたサブセットにのみ数値を出力します//それに対応するビットが//numに設定されている場合。 if（（num＆（1 < =0）{printf（ "{"）; //numのバイナリ表現に対応する//サブセットをPrintintします。サブセット（num_of_bits-1、num、num_of_bits）; printf（ "}"）; //関数を再帰的に呼び出して//次のサブセットを出力します。 printSubSets（num_of_bits、num-1）;それ以外の場合は0を返します。 return 1;} // main programint main（）{int n =4; printSubSets（n、（int）（pow（2、n））-1）;} 
 
出力
 
 {1 2 3 4} {1 2 3} {1 2 4} {1 2} {1 3 4} {1 3} {1 4} {1} {2 3 4} {2 3} {2 4} {2} {3 4} {3} {4} {}