Link: https://leetcode.com/problems/generate-parentheses/
Solution:
Topics: DFS, back tracking
Intuition
The idea here is to build out all possible parentheses using two very simple rules.
- If we have not used up
n
open parentheses, add an open parentheses. - If there are more open parentheses than closed, add a closed parentheses.
Each of these conditions is a branch in our tree.
Implementation
Review 1
The implementation above is not really backtracking…although it could be. In the leetcode editorial they actually do implement backtracking but their way of doing it is super weird. There is actually no point in doing the “pop” part of the backtracking for this problem, but I’ll add it for rigour.
Review 3
Don’t forget to do include open > 0
!