<jupyter_start><jupyter_text>Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.For example, given n = 3, a solution set is:    [      "((()))",      "(()())",      "(())()",      "()(())",      "()()()"    ] Ref:1. [Simple Python DFS solution with explanation](https://leetcode.com/problems/generate-parentheses/discuss/10110/Simple-Python-DFS-solution-with-explanation)2. [[LeetCode] Generate Parentheses 生成括号](https://www.cnblogs.com/grandyang/p/4444160.html)3. [[Leetcode] generate parentheses 生成括号](https://www.cnblogs.com/love-yh/p/7159404.html)<jupyter_code>class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        # hold answer
        res = []
        self.dfs(n, n, '', res)
        return res
    
    # here, left and right denote the remaining nums in the left/right stack
    def dfs(self, left, right, string, res):
        # right stack num should be larger than left ones, or wrong and skip this case
        if left > right:
            return 
        # if no remaining element in two stacks, add new string to res and return 
        if left == 0 and right == 0:
            res.append(string)
            return
        # the left case is very simple, just fill left first and then right
        if left:
            self.dfs(left - 1, right, string + '(', res)
        if right:
            self.dfs(left, right - 1, string + ')', res)
            
# test
n = 3
Solution().generateParenthesis(n)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12950094756790903, 'fraction_numerical': 0.017687934301958308, 'mean_word_length': 2.4360086767895877, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 6, 'https://': 3, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '186656', 'license': 'MIT', 'n_tokens_mistral': 515, 'n_tokens_neox': 476, 'n_words': 145, 'path': 'DSA/string/generateParenthesis.ipynb', 'repo_name': 'lance-lh/Data-Structures-and-Algorithms', 'size': '1583'}