Generate Parentheses

Bài toán

Cho n cặp dấu ngoặc. Hãy viết hàm để sinh ra tất cả các tổ hợp dấu ngoặc hợp lệ.

Ví dụ:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Phân Tích & Tiếp Cận

Sai lầm: Brute Force

Sinh mọi chuỗi độ dài 2n gồm ( và ). Sau đó dùng hàm isValid để lọc. Độ phức tạp $O(2^{2n} \cdot n)$. Quá chậm.

Giải pháp: Backtracking thông minh

Ta chỉ thêm dấu ngoặc nếu biết chắc nó có tiềm năng tạo ra chuỗi hợp lệ. Quy tắc:

1. Chỉ được thêm ( nếu: Số lượng ( đã dùng < n.
2. Chỉ được thêm ) nếu: Số lượng ) đã dùng < Số lượng ( đã dùng. (Không bao giờ được đóng ngoặc khi chưa có mở ngoặc chờ sẵn).
3. Dừng lại (Base Case): Khi độ dài chuỗi bằng 2n.

function generateParenthesis(n: number): string[] {
    const res: string[] = [];

    // openN: Số lượng '(' đã dùng
    // closeN: Số lượng ')' đã dùng
    function backtrack(openN: number, closeN: number, currentString: string) {
        // Base case: Đã hoàn thành 1 chuỗi hợp lệ
        if (openN === n && closeN === n) {
            res.push(currentString);
            return;
        }

        // 1. Thử thêm '('
        if (openN < n) {
            backtrack(openN + 1, closeN, currentString + "(");
        }

        // 2. Thử thêm ')'
        if (closeN < openN) {
            backtrack(openN, closeN + 1, currentString + ")");
        }
    }

    backtrack(0, 0, "");
    return res;
}

• Time Complexity: $O(\frac{4^n}{\sqrt{n}})$ - Đây là số Catalan. (Thực tế chỉ cần hiểu nó xấp xỉ cấp số mũ $O(2^n)$ nhưng được cắt tỉa rất nhiều nhánh vô nghĩa).
• Space Complexity: $O(n)$ - Độ sâu đệ quy tối đa là 2n.

Pattern Nhận Diện

Đây là bài toán kinh điển của Backtracking có điều kiện (Constrained Generation). Thay vì sinh ngẫu nhiên rồi kiểm tra (Generate & Test), ta kiểm tra ngay khi sinh (Pruning - Cắt tỉa nhánh).