印刷{1,2,3、…n}のすべてのサブセットをCプログラム内で配列やループを使用せずに取得します

与えられた正の整数nに対して、配列やループを使用せずに集合{1,2,3,4、... n}のすべての部分集合を印刷する必要があります。

私たちは数字に対して何か言うように、3 sと同様に、集合{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　{}　}
説明: 集合は以下のようになります{1　2　3それから、その部分集合を見つけます
入力:　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に戻ります。

• 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　→関数int subset(int bitn, int num, int num_of_bits)内で
　　　If bitn >= 0
　　　　　　If (num & (1　<< bitn)) != 0
　　　　　　　　　Print num_of_bits　-　bitn
　　　　　　　　　subset(bitn　-　1,　num,　num_of_bits);
　　　　　　別の
　　　　　　　　　戻り値0
　　　　　　戻り値　1
　　　ステップ　2　→関数int printSubSets(int num_of_bits, int num)内で
　　　　　　If (num >= 0)
　　　　　　　　　Print "{ "
　　　　　　　　　functionsubset(num_of_bits　-　1, num, num_of_bits)
　　　　　　　　　Print ""
　　　　　　　　　functionprintSubSets(num_of_bits, num　-　1)
　　　　　　別の
　　　　　　　　　戻り値0
　　　　　　戻り値　1
　　　ステップ　3　→関数int main()内で
　　　　　　int nを宣言し初期化します　4
　　　　　　fucntionprintSubSets(n, (int) (pow(2,　n))　-1)
停止

例

#include <stdio.h>
#include <math.h>
//　この関数は再帰的に以下を印刷します。
//　バイナリに対応するsubset。
//　numの表現。
int subset(int bitn, int num, int num_of_bits) {
　　　if　(bitn　>=　0)　{
　　　　　　//　Print　number　in　given　subset　only
　　　　　　//　if　the　bit　corresponding　to　it
　　　　　　//　is　set　in　num.
　　　　　　if　((num　&　(1　<<　bitn))　!=　0)　{
　　　　　　　　　printf("%d　",　num_of_bits　-　bitn);
　　　　　　}
　　　　　　//　Check　the　next　bit
　　　　　　subset(bitn　-　1,　num,　num_of_bits);
　　　}
　　　else
　　　　　　return　0;
　　　　　　return　1;
}
//function　to　print　the　subsets
int　printSubSets(int　num_of_bits,　int　num)　{
　　　if　(num　>=　0)　{
　　　　　　printf("{　");
　　　　　　//　Printint　the　subsets　corresponding　to
　　　　　　//　the　binary　representation　of　num.
　　　　　　subset(num_of_bits　-　1,　num,　num_of_bits);
　　　　　　printf("}");
　　　　　　//　recursively　calling　the　function　to
　　　　　　//　print　the　next　subset.
　　　　　　printSubSets(num_of_bits,　num　-　1);
　　　}
　　　else
　　　　　　return　0;
　　　　　　return　1;
}
//main　program
int　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　{}　}