In Tất Cả Tổ Hợp Ngoặc Đơn Cân Bằng Trong C++

Trong bài toán này, chúng ta được cho một số nguyên n. Nhiệm vụ là in tất cả các cặp ngoặc đơn cân bằng có độ dài n.

Ngoặc đơn cân bằng là các cặp ngoặc có ký tự đóng tương ứng cho mỗi ký tự mở. Các cặp cũng phải được lồng nhau đúng cách.

Ví dụ để hiểu vấn đề:

Đầu vào: n = 2 → Đầu ra: {}{} {{}}

Để giải quyết, ta cần theo dõi số cặp ngoặc. Số lượng ban đầu là 0. Sau đó gọi đệ quy hàm cho đến khi tổng số cặp ngoặc nhỏ hơn n. Đếm ngoặc, gọi đệ quy dựa trên số lượng. Nếu số ngoặc mở > số ngoặc đóng, đặt ngoặc đóng và tiếp tục với số cặp còn lại. Nếu số ngoặc mở < n, gọi đệ quy cho các cặp ngoặc còn lại.

Ví Dụ

Mã minh họa giải pháp:

#include <iostream>
using namespace std;
#define MAX_COUNT 100

void printParenthesesPairs(int pos, int n, int open, int close) {
    static char str[MAX_COUNT];
    if (close == n) {
        cout << str << endl;
        return;
    } else {
        if (open > close) {
            str[pos] = '}';
            printParenthesesPairs(pos + 1, n, open, close + 1);
        }
        if (open < n) {
            str[pos] = '{';
            printParenthesesPairs(pos + 1, n, open + 1, close);
        }
    }
}

int main() {
    int n = 3;
    cout << "Tất cả cặp ngoặc độ dài " << n << " là:\n";
    if (n > 0)
        printParenthesesPairs(0, n, 0, 0);
    getchar();
    return 0;
}

Đầu Ra

Tất cả cặp ngoặc độ dài 3 là:
{}{}{} {}{{}} {{}}{} {{}{}} {{{}}}