In tất cả cách tách chuỗi trong ngoặc trong C++

Cho một chuỗi, hãy tách thành các chuỗi con và in ra với mỗi chuỗi con được bao quanh bởi cặp ngoặc. Ví dụ: "wxyz" cho ra 8 cách: (w)(x)(y)(z), (w)(x)(yz), (w)(xy)(z), (w)(xyz), (wx)(y)(z), (wx)(yz), (wxy)(z), (wxyz).

Đệ quy

Sử dụng đệ quy với tham số: vị trí hiện tại và chuỗi kết quả. Tại mỗi bước, thử tất cả độ dài chuỗi con bắt đầu từ vị trí hiện tại.

Ví dụ minh họa

#include <iostream>
#include <string>
using namespace std;

void printSubstrings(string str, int index, string out) {
    if (index == str.length()) {
        cout << out << endl;
        return;
    }
    for (int i = index; i < str.length(); i++)
        printSubstrings(str, i+1, out + "(" + str.substr(index, i-index+1) + ")");
}

int main() {
    string str = "wxyz";
    cout << "Các cách tách chuỗi:\n";
    printSubstrings(str, 0, "");
    return 0;
}

Kết quả

(w)(x)(y)(z)
(w)(x)(yz)
(w)(xy)(z)
(w)(xyz)
(wx)(y)(z)
(wx)(yz)
(wxy)(z)
(wxyz)