ปัญหา
ได้รับสตริงหนึ่ง พิมพ์สตริงทั้งหมดที่สร้างได้จากการวางช่องว่างระหว่างตัวอักษร เช่น 'XYZ' → XYZ, XY Z, X YZ, X Y Z
วิธีแก้
หาทุกวิธีการวาง Space ใช้ Recursive: วาง Space ทีละตัว สร้างสตริงใหม่
ตัวอย่างโค้ด
#include <iostream>
#include <cstring>
using namespace std;
void printPattern(char str[], char buff[], int i, int j, int n) {
if (i == n) {
buff[j] = '\0';
cout << buff << endl;
return;
}
buff[j] = str[i];
printPattern(str, buff, i+1, j+1, n); // ไม่วาง Space
buff[j] = ' ';
buff[j+1] = str[i];
printPattern(str, buff, i+1, j+2, n); // วาง Space
}
int main() {
char *str = "XYZ";
int n = strlen(str);
char buf[2*n];
buf[0] = str[0];
cout << "The string generated using space are :\n";
printPattern(str, buf, 1, 1, n);
return 0;
}
ผลลัพธ์
XYZ XY Z X YZ X Y Z
คำอธิบาย
Recursive 2 กระบวนทางที่แต่ละตำแหน่ง: 1) ไม่วาง Space 2) วาง Space ก่อนตัวอักษรถัดไป
เริ่มจาก buff[0] = str[0] (ตัวแรกไม่มี Space นำหน้า) เรียก printPattern ตั้งแต่ i=1, j=1
จำนวนสตริงทั้งหมด = 2^(n-1) สำหรับสตริงยาว n
