이 문제에서는 문자열 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