13. Generate Valid Angle Bracket Sequences

Origin: Generate Valid Angle Bracket Sequences

Given n, return all valid sequences of n pairs of ’<’ and ’>’ with proper nesting.

Examples

Example 1: n = 1 → <>

Example 2: n = 2 → <<>> <><>

Example 3: n = 3 → <<<>>> <<><>> <<>><> <><<>> <><><>

Each sequence is generated by choosing to place ’<’ when remaining > 0, and ’>’ when there is at least one unmatched ’<’.

Constraints

• 0 <= n <= 12
• n is an integer

Input Format

The first line contains a single integer n.

Output Format

Return a STRING_ARRAY containing every valid sequence of 2·n characters.

Sample Input 0

1

Sample Output 0

<>

Sample Input 1

2

Sample Output 1

<<>>
<><>

---

函数契约

// 输入：n（整数，括号对数）
// 输出：字符串列表，所有合法的尖括号序列
// 边界：n=0 → [""] 或 []；n=1 → ["<>"]；n=12 → 最大输出

边界表

场景	返回什么
n = 0	[""] 或 []
n = 1	[”<>“]
正常场景	所有合法序列

Resolution

我的解法

function generateAngleBracketSequences(n: number): string[] {
    const result: string[] = []
    const backtrack = (current: string, open: number, close: number) => {
        if (current.length === 2 * n) {
            result.push(current)
            return
        }
        if (open < n) {
            backtrack(current + '<', open + 1, close)
        }
        if (close < open) {
            backtrack(current + '>', open, close + 1)
        }
    }
    backtrack('', 0, 0)
    return result
}

解题思路

经典回溯。维护两个计数器：open（已放的 < 数量）和 close（已放的 > 数量）。

每一步两个选择：

1. 放 <，前提是 open < n（还没放完）
2. 放 >，前提是 close < open（有未匹配的 <）

当 current.length === 2 * n 时，一个合法序列完成，存入结果。

这个思路和 Day 1 第 8 题的括号验证形成对照：

• 第 8 题：给定一个序列，用栈验证合不合法（LIFO 匹配）
• 第 13 题：生成所有合法序列，用回溯在每一步只做合法选择

复杂度

• 时间：O(2^n × n)，序列数量是第 n 个卡特兰数 C(n) = (2n)! / ((n+1)! × n!)，每个序列长度 2n
• 空间：O(n)，递归栈深度最多 2n

参考来源

• 相关文章：算法解题流程：从读题到提交的七步
• 相关题目：8. Validate Properly Nested Brackets — Day 1 的括号验证（栈），这是生成版