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:

Left node means adding left-bracket, right node means adding right-bracket.
Left brackets' number is always greater or equal to right brackets', otherwise the brackets pairs are invalid.
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

Leetcode No.39 Combination Sum

The second article