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

이 문제를 해결하려면 사전순을 얻을 수 있도록 배열을 정렬해야 합니다. 그런 다음 문자열의 한 요소를 수정하고 모든 하위 문자열을 생성할 나머지 요소를 재귀적으로 호출합니다. 그리고 다음 순열을 얻기 위해 첫 번째 고정 요소를 버립니다.

예시

솔루션 구현을 보여주는 프로그램,

#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