Sequence Generation with Recursion

Sequence generation builds strings or lists under grammar rules—often exponential output, so prune or stream when counts explode.

Why this shows up in the real world

Test data generators, regex expanders, and music motive enumeration.

Core idea (explained for students)

Use recursion on “next symbol choice”; memoize when overlapping partials appear (count-only DP).

Try this in Python

def generate_parenthesis(n: int) -> list[str]:
    res: list[str] = []

    def dfs(opened: int, closed: int, path: list[str]) -> None:
        if len(path) == 2 * n:
            res.append(''.join(path))
            return
        if opened < n:
            path.append('(')
            dfs(opened + 1, closed, path)
            path.pop()
        if closed < opened:
            path.append(')')
            dfs(opened, closed + 1, path)
            path.pop()

    dfs(0, 0, [])
    return res


print(generate_parenthesis(3)[:3])

Common mistakes

• Storing all sequences when only count needed—use DP on positions.
• Duplicate sequences from commutative generators.

Key takeaways

• Switch to iterative deepening if memory tight.
• Canonicalize moves to remove symmetry duplicates.