Generate Parentheses: tại sao brute force tạo hàng triệu chuỗi sai chỉ để tìm năm chuỗi đúng

Đề bài nghe đơn giản đến đáng ngờ: cho n cặp dấu ngoặc, sinh tất cả các tổ hợp dấu ngoặc hợp lệ. Với n = 3 là năm chuỗi. Với n = 8 là 1430. Các chuỗi ngắn. Câu hỏi là bạn đến được chúng như thế nào mà không lãng phí thời gian vào khoảng (2n)! cách sắp xếp không hợp lệ.

Có hai câu trả lời. Một cái đơn giản và đúng. Cái còn lại cũng đơn giản và đúng, nhưng nhanh hơn ba bậc độ lớn ngay ở n khiêm tốn. Sự khác biệt không phải là cấu trúc dữ liệu thông minh — mà là thời điểm bạn quyết định một chuỗi đang xây dựng không đi đến đâu nữa.

Đề bài

Cho n cặp dấu ngoặc, viết hàm sinh tất cả các tổ hợp dấu ngoặc hợp lệ — những chuỗi mà mỗi dấu ngoặc mở đều có dấu ngoặc đóng tương ứng theo đúng thứ tự. Full statement: LeetCode 22.

Ràng buộc:
- 1 <= n <= 8

Constraint n <= 8 buộc bạn nghĩ gì

Constraint duy nhất là 1 <= n <= 8. Rất nhỏ. Output cho n = 8 là 1430 chuỗi độ dài 16. Nếu bạn đang viết một tiện ích tạo template, bạn chạy nó một lần rồi cache kết quả. Không ai ship n = 10^6 ở đây.

Vậy tại sao constraint này lại quan trọng? Vì nó cho phép brute force trong thực tế, trong khi khiến lý luận backtracking trở thành kiến thức thuần túy. Brute force chạy trong micro giây với n = 8. Nhưng (2 * 8)! là 20,922,789,888,000 — hơn hai mươi nghìn tỷ hoán vị trước khi deduplication. Ngay cả khi Python sinh được một trăm triệu hoán vị mỗi giây, bạn vẫn phải chờ nhiều giờ. Constraint cho phép backtracking hoàn thành trong mili giây. Nó không loại trừ cái gì cả — về mặt kỹ thuật bạn có thể pass brute force nhờ deduplication qua set() — nhưng tốc độ tăng factorial mới là lý do tại sao phiên bản pruned tồn tại và đáng tìm hiểu.

Điều khác constraint cho bạn biết: đây là bài toán liệt kê tổ hợp, không phải bài toán tìm kiếm. Bạn không tìm một câu trả lời. Bạn xây dựng tất cả chúng. Điều đó định hình cách tiếp cận một cách cơ bản.

Approach 1: Brute force — sinh tất cả, giữ lại những gì đúng

Cách đọc đề bài trực tiếp nhất: một chuỗi hợp lệ độ dài 2n là một cách sắp xếp nào đó của n dấu mở và n dấu đóng. Sinh tất cả các cách sắp xếp, validate từng cái, thu thập những cái hợp lệ.

from itertools import permutations
from typing import List
 
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        chars = ['('] * n + [')'] * n
        valid = set()
        for perm in permutations(chars):
            candidate = ''.join(perm)
            if self._is_valid(candidate):
                valid.add(candidate)
        return list(valid)
 
    def _is_valid(self, s: str) -> bool:
        balance = 0
        for ch in s:
            if ch == '(':
                balance += 1
            else:
                balance -= 1
                if balance < 0:
                    return False
        return balance == 0

using System;
using System.Collections.Generic;
using System.Linq;
 
public class Solution {
    public IList<string> GenerateParenthesis(int n) {
        char[] chars = new char[2 * n];
        for (int i = 0; i < n; i++) {
            chars[i] = '(';
            chars[i + n] = ')';
        }
        var seen = new HashSet<string>();
        GeneratePermutations(chars, 0, seen);
        return seen.ToList();
    }
 
    private void GeneratePermutations(char[] chars, int start, HashSet<string> seen) {
        if (start == chars.Length) {
            string candidate = new string(chars);
            if (IsValid(candidate)) seen.Add(candidate);
            return;
        }
        for (int i = start; i < chars.Length; i++) {
            Swap(chars, start, i);
            GeneratePermutations(chars, start + 1, seen);
            Swap(chars, start, i);
        }
    }
 
    private void Swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
 
    private bool IsValid(string s) {
        int balance = 0;
        foreach (char c in s) {
            if (c == '(') balance++;
            else {
                balance--;
                if (balance < 0) return false;
            }
        }
        return balance == 0;
    }
}

Độ phức tạp. Time: O((2n)! * n) — sinh (2n)! hoán vị và validate mỗi chuỗi tốn O(n). Space: O((2n)! * n) để lưu tất cả hoán vị trước deduplication. Deduplication bằng set là cần thiết vì permutations(['(','(',')',')']) sẽ sinh cùng một chuỗi "(())" nhiều lần từ các thứ tự swap khác nhau của các ký tự giống nhau.

Hàm validation bản thân nó gọn gàng và đáng biết: duy trì một counter balance, tăng khi gặp (, giảm khi gặp ), trả về false ngay nếu balance âm, trả về balance == 0 ở cuối. Điều này nắm bắt cả hai yêu cầu — không đóng sớm, số lượng bằng nhau.

Approach 2: Backtracking — chỉ xây những gì vẫn có thể hợp lệ

Insight ở đây là bạn không cần sinh một chuỗi hoàn chỉnh rồi mới quyết định nó không hợp lệ. Bạn có thể phát hiện ra tính không hợp lệ ngay khi chuỗi đang xây dựng vi phạm quy tắc. Và quy tắc cho chuỗi chưa hoàn chỉnh rất đơn giản:

• Có thể thêm ( nếu số dấu mở đã đặt nhỏ hơn n.
• Có thể thêm ) nếu số dấu đóng đã đặt nhỏ hơn số dấu mở đã đặt.

Điều kiện thứ hai là chìa khóa. Nó nói: đừng bao giờ đóng một dấu ngoặc chưa được mở. Nếu close < open, thêm ) giữ cho chuỗi còn có thể hợp lệ. Nếu close == open, thêm ) sẽ làm balance âm — cắt tỉa nhánh đó hoàn toàn.

from typing import List
 
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []
 
        def backtrack(current: str, open_count: int, close_count: int) -> None:
            if len(current) == 2 * n:
                result.append(current)
                return
            if open_count < n:
                backtrack(current + '(', open_count + 1, close_count)
            if close_count < open_count:
                backtrack(current + ')', open_count, close_count + 1)
 
        backtrack('', 0, 0)
        return result

using System.Collections.Generic;
 
public class Solution {
    public IList<string> GenerateParenthesis(int n) {
        var result = new List<string>();
        Backtrack("", 0, 0, n, result);
        return result;
    }
 
    private void Backtrack(string current, int openCount, int closeCount, int n, List<string> result) {
        if (current.Length == 2 * n) {
            result.Add(current);
            return;
        }
        if (openCount < n)
            Backtrack(current + "(", openCount + 1, closeCount, n, result);
        if (closeCount < openCount)
            Backtrack(current + ")", openCount, closeCount + 1, n, result);
    }
}

Độ phức tạp. Time: O(4^n / sqrt(n)) — đây là số Catalan thứ n, đếm chính xác số chuỗi dấu ngoặc hợp lệ. Mỗi lần gọi ở base case tạo ra một kết quả; không có chuỗi không hợp lệ nào được xây dựng đầy đủ. Space: O(4^n / sqrt(n)) cho output, cộng thêm O(n) cho call stack (độ sâu tối đa 2n).

Phân tích space quan trọng ở đây. Call stack là O(n). List output là O(4^n / sqrt(n) * n) vì bạn lưu toàn bộ chuỗi cho mỗi tổ hợp hợp lệ. Nếu ai đó hỏi "tại sao không phải O(n)", câu trả lời là bạn phải lưu kết quả đâu đó.

Trace tay: n = 2 qua decision tree

Đi qua từng bước bằng tay, bắt đầu từ chuỗi rỗng:

• open=0, close=0: chỉ được phép thêm ( (không thể đóng khi chưa mở). Thêm (.
• open=1, close=0: có thể thêm ( (open < n=2) hoặc ) (close < open=1). Rẽ nhánh cả hai.
  • Nhánh trái thêm ( -> ((, open=2, close=0
  • Nhánh phải thêm ) -> (), open=1, close=1
• Từ (( với open=2, close=0: không thể thêm ( (open == n). Phải thêm ). -> ((), open=2, close=1
• Từ (() với open=2, close=1: không thể thêm (. Thêm ) -> (()), độ dài 4, emit.
• Từ () với open=1, close=1: có thể thêm ( (open < n=2) hoặc ). Nhưng close == open, nên không thể thêm ). Thêm ( -> ()(, open=2, close=1.
• Từ ()( với open=2, close=1: không thể thêm (. Thêm ) -> ()(), độ dài 4, emit.

Kết quả: ["(())", "()()"]. Cả hai chuỗi được tìm thấy, không có một candidate không hợp lệ nào được khám phá.

Các edge case

n = 1: chỉ có một chuỗi hợp lệ, "()". Backtrack bắt đầu với open=0, close=0, thêm (, sau đó phải thêm ), đạt độ dài 2, emit. Một đường gọi, một kết quả. Brute force cho n=1 thực ra ổn: permutations(['(', ')']) cho hai cách sắp xếp, một cái hợp lệ. Khoảng cách chỉ mở ra ở n cao hơn.

n = 8 (lớn nhất): 1430 kết quả. Backtracking khám phá đúng 1430 leaf node. Brute force cần sinh và hash (16)! / (8! * 8!) = 12870 cách sắp xếp phân biệt từ góc nhìn combinations — nhưng permutations sinh 16! tổng cộng, khoảng 2 * 10^13. Tỉ lệ đó (2 * 10^13 so với 1430) là lý do backtracking quan trọng ngay cả khi constraint nhỏ.

Tất cả dấu mở trước, rồi tất cả dấu đóng: ((())) với n=3 — hoàn toàn hợp lệ. Backtracking đến được nó bằng cách luôn chọn nhánh mở trước khi có thể. Đây là leaf đầu tiên trong DFS traversal.

Tại sao không có n = 0?: Constraint nói 1 <= n. Nhưng nếu bạn truyền n = 0, backtrack bắt đầu với len('') == 0 == 2 * 0, ngay lập tức emit chuỗi rỗng, và trả về ['']. Điều đó có thể coi là đúng cho zero cặp.

Pruning invariant, phát biểu chính xác

Tính đúng đắn của backtracking dựa trên một khẳng định: nếu tại bất kỳ thời điểm nào close >= open, mọi cách hoàn thành chuỗi hiện tại đều không hợp lệ. Chứng minh: bạn cần thêm đủ ) để khớp với tất cả (, nhưng bạn đã thêm nhiều ) như (, nên bất kỳ ) nào thêm nữa sẽ vượt quá số lượng (, làm balance âm tại một vị trí nào đó. Pruning không chỉ là tối ưu hóa — nó tương đương logic với việc kiểm tra tính hợp lệ trong brute force, chỉ là áp dụng sớm hơn.

Tương tự, open > n luôn không hợp lệ: bạn không thể dùng nhiều ( hơn tổng số n cặp.

Hai điều kiện pruning này cùng nhau đảm bảo rằng mọi chuỗi đạt độ dài 2n trong backtracking đều hợp lệ. Không cần validation pass sau đó.

Bảng so sánh

Với n = 8: brute force thăm ~10^13 state; backtracking thăm 1430. Các O class không nắm bắt được khoảng cách này — các con số cụ thể mới làm điều đó.

Cái gì tôi sẽ ship và tại sao

Backtracking, ngay lập tức. Không phải vì khoảng cách hiệu suất — với n <= 8 khoảng cách đó là học thuật — mà vì code trực tiếp mã hóa các quy tắc cấu trúc của dấu ngoặc hợp lệ. Ai đọc if close_count < open_count đều hiểu tại sao dòng đó ở đó: bạn chỉ có thể đóng dấu ngoặc đã được mở. Phiên bản brute force buộc người đọc phải trace qua việc sinh hoán vị, deduplication bằng set, và một validity check riêng biệt. Phiên bản backtracking là đề bài viết thành code.

Trường hợp duy nhất tôi sẽ dùng brute force là nếu tôi đang tạo prototype một validator cho định dạng output nào đó và tình cờ cần một tập hợp đã biết là hợp lệ để test. Trong trường hợp đó, sự rõ ràng của "sinh tất cả, lọc" hấp dẫn chính xác vì logic lọc được cô lập và có thể test riêng.

Pattern mà bài này dạy

Generate Parentheses là ví dụ kinh điển của constrained enumeration via backtracking. Pattern như sau:

• Bạn đang xây dựng một chuỗi từng phần tử một.
• Tại mỗi bước, một tập quy tắc xác định những phần tử nào là lựa chọn tiếp theo hợp lệ.
• Bạn áp dụng các quy tắc đó tại thời điểm xây dựng, không phải tại thời điểm validation.
• Bất kỳ trạng thái nào vi phạm quy tắc đều bị cắt tỉa ngay — bạn không bao giờ mở rộng nó thêm.

Pattern này chuyển giao trực tiếp sang: letter combinations (LeetCode 17), subsets (LeetCode 78), permutations (LeetCode 46), combination sum (LeetCode 39). Điều kiện pruning cụ thể thay đổi, nhưng skeleton không đổi.

Số chuỗi dấu ngoặc hợp lệ cho n cặp là số Catalan thứ n: C(n) = C(2n, n) / (n + 1). Số Catalan xuất hiện trong liệt kê binary tree, triangulation đa giác, và stack-sortable permutation — tất cả các bài toán với cùng cấu trúc constraint cơ bản. Nhận ra rằng số output của bạn bị giới hạn bởi Catalan là dấu hiệu backtracking là công cụ phù hợp.

Vị trí của bài này trong series stack

Series đã đề cập Valid Parentheses (20) — kiểm tra xem một chuỗi có hợp lệ không — và Evaluate Reverse Polish Notation (150) — dùng stack để tính biểu thức. Generate Parentheses là phần bù constructive của Valid Parentheses: thay vì kiểm tra, bạn đang xây dựng. Sự đảo ngược đó là bước khái niệm.

Logic validity từ bài 20 xuất hiện ở đây như điều kiện pruning. Bạn đã biết balance >= 0 tại mọi prefix và balance == 0 ở cuối là hai yêu cầu. Ở đây bạn enforce chúng trong lúc xây dựng thay vì sau đó.

Letter Combinations of a Phone Number (17) có cùng skeleton backtracking. Constraint không phải là cân bằng open/close mà là mapping từ chữ số đến tập ký tự. Độ sâu cố định (một ký tự mỗi chữ số), và tại mỗi level bạn rẽ nhánh theo tập ký tự. Cùng cấu trúc, điều kiện rẽ nhánh khác.

Remove Invalid Parentheses (301) đảo ngược hướng: cho một chuỗi có thể không hợp lệ, tìm tất cả các cách xóa số ký tự tối thiểu để làm nó hợp lệ. Bây giờ bạn đang tìm kiếm trong không gian các lần xóa thay vì xây từ đầu. Validity check giống nhau; hướng tìm kiếm đảo ngược.

Different Ways to Add Parentheses (241) hỏi có bao nhiêu cách bạn có thể đặt dấu ngoặc vào một biểu thức số học. Câu trả lời liên quan đến số Catalan theo một dạng khác — bạn đang đếm parse tree thay vì chuỗi, nhưng cấu trúc tổ hợp giống hệt nhau.