Algorithm_study/Generate Parentheses.py at main · HakSooDev/Algorithm_study · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# https://leetcode.com/problems/generate-parentheses/
# Hak Soo Kim
# 2/8/2022

class Solution(object):
    def generateParenthesis(self, n):
        ans = []
        self.generate(ans, 0, 0, 0, n, "")
        return (ans)
        """
        :type n: int
        :rtype: List[str]
        """

    def generate(self, ans, openCounter, closeCounter, counter, n, string):
        if (counter == 2 * n):
            ans.append(string)
            return
        if (openCounter < n):
            self.generate(ans, openCounter + 1, closeCounter, counter + 1, n, string + "(")
        if (closeCounter < openCounter):
            self.generate(ans, openCounter, closeCounter + 1, counter + 1, n, string + ")")

# Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
#
# Example 1:
#
# Input: n = 3
# Output: ["((()))","(()())","(())()","()(())","()()()"]
# Example 2:
#
# Input: n = 1
# Output: ["()"]
#
# Constraints:
#
# 1 <= n <= 8