Biểu thức ngoặc cân bằng với vị trí mở ngoặc cho trước trong C++

Cho số nguyên n và mảng vị trí position[] (1 ≤ length ≤ 2n), tìm số cách tạo biểu thức ngoặc đúng độ dài 2n sao cho các vị trí cho trước phải là ngoặc mở.

Lưu ý: Mảng position[] dùng chỉ số 1-based, ví dụ [0,1,1,0]. Giá trị 1 = vị trí bắt buộc là ngoặc mở. Giá trị 0 = có thể là mở hoặc đóng.

Ví dụ

Input: n = 2, position[] = [1, 0, 1, 0]
Output: 1
Chỉ có khả năng: [ ] [ ]

Giải thích đệ quy và đệ quy có nhớ (memoization).

Thuật toán

• Đánh dấu vị trí bắt buộc mở ngoặc trong mảng adj = 1.
• Đệ quy:
  • Nếu số ngoặc mở - đóng < 0 → trả về 0.
  • Nếu chỉ số đạt 2n và chênh lệch = 0 → tìm thấy nghiệm, trả về 1; ngược lại 0.
  • Nếu vị trí hiện tại = 1 → đệ quy index+1, tăng chênh lệch.
  • Ngược lại → đệ quy hai nhánh: đặt mở (tăng chênh lệch) hoặc đóng (giảm chênh lệch), cộng kết quả.

Giải pháp đệ quy

// Đệ quy
#include <bits/stdc++.h>
using namespace std;

int find(int index1, int openbrk1, int m, int adj1[]) {
    if (openbrk1 < 0) return 0;
    if (index1 == m) {
        if (openbrk1 == 0) return 1;
        else return 0;
    }
    if (adj1[index1] == 1)
        return find(index1 + 1, openbrk1 + 1, m, adj1);
    else
        return find(index1 + 1, openbrk1 + 1, m, adj1)
             + find(index1 + 1, openbrk1 - 1, m, adj1);
}

int main() {
    int m = 2;
    int adj1[4] = {1, 0, 0, 0};
    cout << find(0, 0, 2 * m, adj1) << endl;
    return 0;
}

Kết quả: 2

Cách nhớ (Memoization) – Tối ưu O(N²)

// Memoization
#include <bits/stdc++.h>
using namespace std;
#define M 1000

int find(int index1, int openbrk1, int m, int dp1[M][M], int adj1[]) {
    if (openbrk1 < 0) return 0;
    if (index1 == m) {
        if (openbrk1 == 0) return 1;
        else return 0;
    }
    if (dp1[index1][openbrk1] != -1)
        return dp1[index1][openbrk1];
    if (adj1[index1] == 1)
        dp1[index1][openbrk1] = find(index1 + 1, openbrk1 + 1, m, dp1, adj1);
    else
        dp1[index1][openbrk1] = find(index1 + 1, openbrk1 + 1, m, dp1, adj1)
                             + find(index1 + 1, openbrk1 - 1, m, dp1, adj1);
    return dp1[index1][openbrk1];
}

int main() {
    int dp1[M][M];
    int m = 2;
    memset(dp1, -1, sizeof(dp1));
    int adj1[4] = {1, 0, 0, 0};
    cout << find(0, 0, 2 * m, dp1, adj1) << endl;
    return 0;
}

Kết quả: 2

Độ phức tạp thời gian: O(N²)