In tất cả chuỗi chèn dấu cách vào chuỗi gốc C++

Cho chuỗi, in tất cả chuỗi có thể tạo bằng cách chèn dấu cách giữa các ký tự.

Ví dụ

Input: "XYZ" → Output: "XYZ", "XY Z", "X YZ", "X Y Z"

Với n ký tự, có n-1 vị trí chèn → 2^(n-1) khả năng.

Thuật toán đệ quy

Duyệt từng ký tự, tại mỗi bước: 1) không chèn space, 2) chèn space trước ký tự hiện tại (trừ ký tự đầu).

Chương trình mẫu

#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;
    }
    // Không chèn space
    buff[j] = str[i];
    printPattern(str, buff, i + 1, j + 1, n);
    
    // Chèn space (chỉ nếu không phải ký tự đầu)
    if (i > 0) {
        buff[j] = ' ';
        buff[j + 1] = str[i];
        printPattern(str, buff, i + 1, j + 2, n);
    }
}

int main() {
    char *str = "XYZ";
    int n = strlen(str);
    char buf[2 * n];
    buf[0] = str[0]; // Ký tự đầu luôn không space trước
    cout << "Strings with spaces:\n";
    printPattern(str, buf, 1, 1, n);
    return 0;
}

Kết quả

XYZ
XY Z
X YZ
X Y Z

Giải thích: Ký tự đầu tiên cố định không space trước. Từ ký tự thứ 2, mỗi ký tự có 2 lựa chọn: có space trước hoặc không.

Độ phức tạp: O(n × 2^n) thời gian (2^(n-1) chuỗi, mỗi chuỗi in O(n)), O(n) stack space.