คำอธิบายปัญหา
ในปัญหานี้ เราได้รับสตริง และเราต้องแบ่งมันเป็นซับสตริง (substrings) และพิมพ์พวกมันโดยล้อมรอบด้วยวงเล็บ
ลองดูตัวอย่างเพื่อเข้าใจปัญหาให้ดีขึ้น:
Input : wxyz Output : (w) (x) (y) (z) (w) (x) (yz) (w) (xy) (z) (w) (xyz) (wx) (y) (z) (wx) (yz) (wxy) (z) (wxyz)
คำอธิบาย – เราจะแบ่งสตริงเป็นซับสตริงที่เป็นไปได้ทั้งหมด และล้อมแต่ละซับสตริงด้วยวงเล็บ
ตอนนี้ เราเข้าใจปัญหาแล้ว มาสร้างโซลูชันกัน
ที่นี่ เราจะใช้ recursion (การเรียกซ้ำ) เพื่อแก้ปัญหา เราจะใช้สองพารามิเตอร์ หนึ่งคือตัวอักษรถัดไปของสตริง และอีกอันคือสตริงผลลัพธ์ สตริงที่ยังไม่ได้ประมวลผลจะถูกประมวลผลทีละน้อยในแต่ละการวนรอบ และสร้าง subsets ขึ้นมา
ตัวอย่างโค้ด
โปรแกรมแก้ปัญหา:
#include <iostream> using namespace std; void substring(string str, int index, string out){ if (index == str.length()) cout << out << endl; for (int i = index; i < str.length(); i++) substring(str, i + 1, out + "(" + str.substr(index, i+1-index) + ")" ); } int main(){ string str = "wxyz"; cout<<"The substring are : "<<endl; substring(str, 0, ""); return 0; }ผลลัพธ์
The substring are : (w)(x)(y)(z) (w)(x)(yz) (w)(xy)(z) (w)(xyz) (wx)(y)(z) (wx)(yz) (wxy)(z) (wxyz)
