AI Hints
Home›DSA in Python Tutorial›More Practice: Backtracking and Graphs
DSA in Python · Lesson 121 of 132

Practice: Generate Parentheses

Backtracking with rules.

⏱ 2 min read▶ Video at 2:24:18🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Write every valid way to arrange three pairs of brackets. Valid means every opening bracket gets closed, in the right order. Pause. When is it allowed to add an opening bracket, and when a closing one?

Practice: Generate Parentheses
From the video: Practice: Generate Parentheses
  • Three pairs of brackets
  • Every valid arrangement
  • When can we add each kind?

Two simple rules

We build the string one bracket at a time. We may add an opening bracket if we haven't used all of them. We may add a closing bracket only if there are more opens than closes so far. When the string is full, it's valid, so we keep it. Run it. Five arrangements.

parens.pypython
def generate(n):
    out = []
    def build(s, opened, closed):
        if len(s) == 2 * n:
            out.append(s)
            return
        if opened < n:
            build(s + "(", opened + 1, closed)
        if closed < opened:
            build(s + ")", opened, closed + 1)
    build("", 0, 0)
    return out

print(generate(3))
Output
['((()))', '(()())', '(())()', '()(())', '()()()']

Pruning makes it fast

Without the rules, we'd build all sixty four strings of six brackets, and check each one. The rules stop bad strings as soon as they start, so we only ever build valid ones. That's the heart of good backtracking. Prune early.

keyvalue
Openif opened < n
Closeif closed < opened
Fullkeep it
Keyprune early

Summary

Generate parentheses with backtracking, using two rules that only allow valid strings. Next, finding cycles in a graph.

Key takeaways
  • Add open if any left
  • Close only if open
  • Prune early
Next up: Practice: Detect a Cycle — three colours