22. Generate Parentheses

Problem

Đề bài yêu cầu cần tạo tất cả các tổ hợp dấu ngoặc tròn hợp lệ với n cặp dấu ngoặc

Approach

Đệ quy và backtrack

Sử dụng đệ quy để xây dựng các chuỗi dấu ngoặc từng bước

Tại mỗi bước, có thể thêm một dấu ngoặc “(” hoặc “)” vào chuỗi hiện tại, miễn là chúng hợp lệ

Điều kiện hợp lệ:

Số lượng dấu ngoặc mở không được vượt quá n

Số lượng dấu ngoặc đóng không được nhiều hơn số lượng dấu ngoặc mở

Time and space complexity

TC: O(2n! / n!(n+ 1)!) = O(n * Cn) - số lượng tổ hợp, dãy số catalan cho n cặp dấu ngoặc (Số catalan tăng rất nhanh theo cấp số nhân)

SC: O(n * Cn), recursive stack

Solution

typescripttypescript

1function generateParenthesis(n: number): string[] {
2    const res: string[] = [];
3
4    function backtrack(current: string, open: number, close: number): void {
5        if (current.length === 2 * n) {
6            res.push(current);
7            return;
8        }
9
10        if (open < n) {
11            backtrack(current + "(", open + 1, close);
12        }
13
14        if (close < open) {
15            backtrack(current + ")", open, close + 1);
16        }
17    }
18
19    backtrack("", 0, 0);
20    return res;
21}

💡

Tóm tắt

open : Số ngoặc mở đã dùng

close : Số ngoặc đóng đã dùng

Luôn đảm bảo close <= open <= n để chuỗi hợp lệ

💡

Tưởng tượng backtrack

Bạn có thể tưởng tượng backtrack như việc duyệt một cây. Mỗi đỉnh (node) trên cây là một trạng thái của bài toán (ở đây là chuỗi ngoặc hiện tại có cùng số lượng ngoặc mở / đóng)

Mỗi lần gọi đệ quy là bạn đi xuống một nhánh con (child) của cây

Khi một nhánh đã đi hết (đạt điều kiện dừng hoặc không còn lựa chọn hợp lệ), thuật toán sẽ backtrack, về node cha để thử tiếp các nhánh con (sibling) khác chưa duyệt ở node nào đó

Minh họa cụ thể

typescripttypescript

1         ""
2        /   \
3      (      )
4     /        \
5   ((         ()
6   / \        / \
7 (() ())   ()(  ())
8

Khi đi hết một nhánh (ví dụ "(()"), thuật toán quay lại node cha ("((") để thử nhánh sibling còn lại ("(((" nếu có).

Khi mọi nhánh con của một node đã được duyệt, thuật toán tiếp tục backtrack lên node cha cao hơn, và cứ thế cho đến khi duyệt hết toàn bộ cây

Bản chất

Backtrack chính là quá trình "quay lại" các node cha để thử các nhánh sibling tiếp theo, đảm bảo không bỏ sót bất kỳ cấu hình nào có thể xảy ra5.

Quá trình này giống như duyệt cây theo chiều sâu (Depth-First Search)

Loading content...

1function generateParenthesis(n: number): string[] { 2 const res: string[] = []; 3 4 function backtrack(current: string, open: number, close: number): void { 5 if (current.length === 2 * n) { 6 res.push(current); 7 return; 8 } 9 10 if (open < n) { 11 backtrack(current + "(", open + 1, close); 12 } 13 14 if (close < open) { 15 backtrack(current + ")", open, close + 1); 16 } 17 } 18 19 backtrack("", 0, 0); 20 return res; 21}

22. Generate Parentheses

Related Posts

Related Posts

22. Generate Parentheses

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists