C++で辞書式順序でべき集合

この問題では、文字列strが与えられます。私たちのタスクは、この文字列の要素のべき集合を辞書式順序で印刷することです。

パワーセット −セットのべき集合は、セットのすべてのサブセットのセットです。 P（S）で示されます。ここで、sはセットです。

例 −

S = {1, 2, 3} ;
p(S) = {{}, {1}, {1, 2}, {1, 3}, {2}, {2, 3}, {3}, {1,2,3}}

この問題では、文字列をセットとして扱います。したがって、そのキャラクターはセットの要素になります。

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

入力 − str =“ xyz”

出力 − x xy xyz xz y yz z

この問題を解決するには、辞書式順序を取得できるように配列を並べ替える必要があります。次に、文字列の1つの要素を修正し、残りの要素を再帰的に呼び出して、すべてのサブ文字列を生成します。そして、最初の固定要素を破棄して、次の順列を取得します。

例

ソリューションの実装を示すプログラム

#include <bits/stdc++.h>
using namespace std;
void printAllSubsets(string str, int n, int index = -1, string subset = "") {
   if (index == n)
      return;
   cout<<subset<<"\n";
   for (int i = index + 1; i < n; i++) {
      subset+= str[i];
      printAllSubsets(str, n, i, subset);
      subset = subset.erase(subset.size() - 1);
   }
   return;
}
void GeneratePowerSet(string str) {
   sort(str.begin(), str.end());
   printAllSubsets(str, str.size());
}
int main() {
   string str = "xyz";
   cout<<"Power Set of the string '"<<str<<"' is :\n";
   GeneratePowerSet(str);
   return 0;
}

出力

Power Set of the string 'xyz' is:
x xy xyz xz y yz z