ในปัญหานี้ ให้สตริง str ต้องพิมพ์ Power Set ของตัวอักษรในสตริง โดยเรียงตามลำดับ Lexicographic (พจนานุกรม)
Power Set คืออะไร?
Power Set ของเซต S คือ เซตของทุกซับเซตของ S สัญลักษณ์ P(S)
S = {1, 2, 3}
P(S) = {{}, {1}, {1, 2}, {1, 3}, {2}, {2, 3}, {3}, {1,2,3}}
ในที่นี้ถือตัวอักษรในสตริงเป็นสมาชิกของเซต
ตัวอย่าง
Input − str = "xyz"
Output − x xy xyz xz y yz z
วิธีแก้
- เรียงตัวอักษรในสตริงให้เป็นลำดับ lexicographic ก่อน
- ใช้ Recursion: เลือกตัวอักษรตัวหนึ่ง แล้วเรียกหาซับเซตของตัวที่เหลือ
- Backtracking: ลบตัวอักษรที่เลือกออก เพื่อหาการจัดเรียงถัดไป
ตัวอย่างโค้ด C++
#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.erase(subset.size() - 1); // backtrack
}
}
void GeneratePowerSet(string str) {
sort(str.begin(), str.end()); // เรียงให้เป็น lexicographic order
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
หมายเหตุ
เซตว่าง {} ไม่ได้แสดงในตัวอย่างนี้ (index เริ่มที่ -1 และพิมพ์ subset ก่อนวนลูป)
