Leetcode No.22 Generate Parentheses
2022/10/26The dfs solution to leetcode no. 22. Medium level.
algorithm
dfs


Question

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Examples
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Input: n = 1
Output: ["()"]

Solution

Using Deep First Search(DFS), we have the following three rules:

  1. Left node means adding left-bracket, right node means adding right-bracket.
  2. Left brackets' number is always greater or equal to right brackets', otherwise the brackets pairs are invalid.
  3. When left brackets' number is equal to right brackets' and is equal to the given n, the search reached the end.
dfs
python
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def dfs(s: str, l: int, r: int):
            if r == l:
                if l < n:
                    # only go to left node, avoiding r-bracket more than l-bracket
                    dfs(s+'(', l+1, r)
                else:
                    # bracket num reached n, get one solution 
                    ans.append(s)
            else:
                if l < n:
                    dfs(s+'(', l+1, r)
                    dfs(s+')', l, r+1)
                else:
                    dfs(s+')', l, r+1)
        dfs('', 0, 0)
        return ans

dfs

Designed & Coded by Tianyu @2022~2023