generate_parentheses

View Source

 1# @leet start
 2class Solution:
 3    def generateParenthesis(self, n: int) -> list[str]:
 4        """
 5        This problem asks to generate all balanced parentheses strings given
 6        a number `n`, the count of open and closed parens.
 7
 8        Since we have two choices at every branch (either add an opening or closing paren)
 9        We know this is going to be $2^n$ time at least, so the input size cannot be big.
10
11        So for every string, we can either add an opening or a closing paren.
12        If the count of open parens == closed parens, then we can only add an open paren.
13        If the count of open parens > closed parens, we can only add an open paren.
14
15        We know this because if there's an empty string and a closed paren is added,
16        the parens become unbalanced. Thus, any state which is equivalent to an empty string
17        (when the count of open parens == closed parens), we can only add an open paren.
18        """
19        res = []
20
21        def recurse(s):
22            left = s.count("(")
23            right = s.count(")")
24            if len(s) == 2 * n:
25                res.append(s)
26                return
27
28            if left < n:
29                recurse(s + "(")
30
31            if right < n and right < left:
32                recurse(s + ")")
33
34        recurse("")
35
36        return res
37
38
39# @leet end
40sol = Solution()
41
42
43def test():
44    assert sol.generateParenthesis(0) == [""]
45    assert sol.generateParenthesis(1) == ["()"]
46    assert sol.generateParenthesis(2) == ["()()", "(())"]
47    assert sol.generateParenthesis(3) == [
48        "((()))",
49        "(()())",
50        "(())()",
51        "()(())",
52        "()()()",
53    ]

class Solution: View Source

 3class Solution:
 4    def generateParenthesis(self, n: int) -> list[str]:
 5        """
 6        This problem asks to generate all balanced parentheses strings given
 7        a number `n`, the count of open and closed parens.
 8
 9        Since we have two choices at every branch (either add an opening or closing paren)
10        We know this is going to be $2^n$ time at least, so the input size cannot be big.
11
12        So for every string, we can either add an opening or a closing paren.
13        If the count of open parens == closed parens, then we can only add an open paren.
14        If the count of open parens > closed parens, we can only add an open paren.
15
16        We know this because if there's an empty string and a closed paren is added,
17        the parens become unbalanced. Thus, any state which is equivalent to an empty string
18        (when the count of open parens == closed parens), we can only add an open paren.
19        """
20        res = []
21
22        def recurse(s):
23            left = s.count("(")
24            right = s.count(")")
25            if len(s) == 2 * n:
26                res.append(s)
27                return
28
29            if left < n:
30                recurse(s + "(")
31
32            if right < n and right < left:
33                recurse(s + ")")
34
35        recurse("")
36
37        return res

def generateParenthesis(self, n: int) -> list[str]: View Source

 4    def generateParenthesis(self, n: int) -> list[str]:
 5        """
 6        This problem asks to generate all balanced parentheses strings given
 7        a number `n`, the count of open and closed parens.
 8
 9        Since we have two choices at every branch (either add an opening or closing paren)
10        We know this is going to be $2^n$ time at least, so the input size cannot be big.
11
12        So for every string, we can either add an opening or a closing paren.
13        If the count of open parens == closed parens, then we can only add an open paren.
14        If the count of open parens > closed parens, we can only add an open paren.
15
16        We know this because if there's an empty string and a closed paren is added,
17        the parens become unbalanced. Thus, any state which is equivalent to an empty string
18        (when the count of open parens == closed parens), we can only add an open paren.
19        """
20        res = []
21
22        def recurse(s):
23            left = s.count("(")
24            right = s.count(")")
25            if len(s) == 2 * n:
26                res.append(s)
27                return
28
29            if left < n:
30                recurse(s + "(")
31
32            if right < n and right < left:
33                recurse(s + ")")
34
35        recurse("")
36
37        return res

This problem asks to generate all balanced parentheses strings given a number n, the count of open and closed parens.

Since we have two choices at every branch (either add an opening or closing paren) We know this is going to be $2^n$ time at least, so the input size cannot be big.

So for every string, we can either add an opening or a closing paren. If the count of open parens == closed parens, then we can only add an open paren. If the count of open parens > closed parens, we can only add an open paren.

We know this because if there's an empty string and a closed paren is added, the parens become unbalanced. Thus, any state which is equivalent to an empty string (when the count of open parens == closed parens), we can only add an open paren.

sol = <Solution object>

def test(): View Source

44def test():
45    assert sol.generateParenthesis(0) == [""]
46    assert sol.generateParenthesis(1) == ["()"]
47    assert sol.generateParenthesis(2) == ["()()", "(())"]
48    assert sol.generateParenthesis(3) == [
49        "((()))",
50        "(()())",
51        "(())()",
52        "()(())",
53        "()()()",
54    ]