LeetCode #22 Generate Parentheses

Posted on | Post modified | In , , , ,

Problem

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

Example

given n = 3, a solution set is:

1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution1

Method: Recursive Depth First Search

Time Complexity:

Space Complexity:

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
class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if not n:
            return []
        left, right, ans = n, n, []
        self.dfs(left,right, ans, "")
        return ans

    def dfs(self, left, right, ans, string):
        """
        :type left: int
        :type right: int
        :type ans: List[str]
        :type string: str
        """
        if right < left:
            return
        if not left and not right:
            ans.append(string)
            return
        if left:
            self.dfs(left - 1, right, ans, string + "(")
        if right:
            self.dfs(left, right - 1, ans, string + ")")

Solution2

Method: Backtracking

Time Complexity:

Space Complexity:

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
class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        ret = []

        def construct_candidates(answer, kth, info):
            candidates = []
            left = answer.count('(')
            right = answer.count(')')
            if left < info:
                candidates.append('(')
            if right < left:
                candidates.append(')')
            return candidates
        
        def backtracking(answer, kth, info):
            if kth == 2*info:
                ret.append(''.join(answer[:]))
            else:
                kth += 1
                candidates = construct_candidates(answer, kth, info)
                for candidate in candidates:
                    answer[kth - 1] = candidate
                    backtracking(answer[:], kth, info)

        backtracking([0 for _ in range(2*n)], 0, n)
        
        return ret

or

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
38
39
40
41
class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        ret = []

        def construct_candidates(answer, kth, info):
            candidates = []
            left = answer[1]
            right = answer[2]
            if left < info:
                candidates.append('(')
            if right < left:
                candidates.append(')')
            return candidates
        
        def backtracking(answer, kth, info):
            if kth == 2*info:
                ret.append(''.join(answer[0]))
            else:
                kth += 1
                candidates = construct_candidates(answer, kth, info)
                for candidate in candidates:
                    answer[0][kth - 1] = candidate
                    if candidate == '(':
                        answer[1] += 1
                    else:
                        answer[2] += 1
                    
                    backtracking(answer[:], kth, info)
                    
                    if candidate == '(':
                        answer[1] -= 1
                    else:
                        answer[2] -= 1
                    
        backtracking([[0 for _ in range(2*n)], 0, 0], 0, n)
        
        return ret