Teaching Kids Programming – Back Tracking Algorithm to Generate Parentheses

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Bruteforce Algorithm to Generate Parentheses

The overall string should be 2 times of n. We can bruteforce all possibilities – each character could be either ‘(‘ or ‘)’ which gives 2^(2n) time complexity. And then we check if the result string is a valid Parentheses – this takes additional O(N).

Overall complexity is O(2^(2N) * N).

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

class Solution(object):
    def generateParenthesis(self, n):
        def dfs(A = []):
            if len(A) == 2*n:
                if validParentheses(A):
                    ans.append("".join(A))
            else:
                A.append('(')
                dfs(A)
                A.pop()
                A.append(')')
                dfs(A)
                A.pop()
 
        def validParentheses(A):
            bal = 0
            for c in A:
                if c == '(': bal += 1
                else: bal -= 1
                if bal < 0: return False
            return bal == 0
 
        ans = []
        dfs()
        return ans

class Solution(object):
    def generateParenthesis(self, n):
        def dfs(A = []):
            if len(A) == 2*n:
                if validParentheses(A):
                    ans.append("".join(A))
            else:
                A.append('(')
                dfs(A)
                A.pop()
                A.append(')')
                dfs(A)
                A.pop()

        def validParentheses(A):
            bal = 0
            for c in A:
                if c == '(': bal += 1
                else: bal -= 1
                if bal < 0: return False
            return bal == 0

        ans = []
        dfs()
        return ans

Backtracking Algorithm to Generate Parentheses

For most generations like the bruteforce algorithm (above), they are invalid. We can backtrack when there is no way to generate a valid Parentheses. To achieve this, we can record the current number of opening Parentheses and the closing Parentheses.

Backtracking algorithms are basically the Depth First Search with branches cut-offs when certain conditions are met (rewind).

If the closing Parentheses is equal or more than the opening Parentheses, there is no point to add opening Parentheses. Similarly, if current number of Parentheses is a which is smaller than n, we can append opening bracket “(“.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def dfs(cur, a, b):
            nonlocal ans
            if a + b == n + n:
                if a == b:
                    ans.append(cur)
                return
            if a < n:
                dfs(cur + "(", a + 1, b)
            if a > b:
                dfs(cur + ")", a, b + 1)                                
        dfs("", 0, 0)
        return ans

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def dfs(cur, a, b):
            nonlocal ans
            if a + b == n + n:
                if a == b:
                    ans.append(cur)
                return
            if a < n:
                dfs(cur + "(", a + 1, b)
            if a > b:
                dfs(cur + ")", a, b + 1)                                
        dfs("", 0, 0)
        return ans

Time and space complexity is O(4^n/sqrt(n)) – i.e. n-th Catalan number.

Generate Parentheses Algorithms:

• How to Generate Parentheses using Bruteforce or Depth First Search (Backtracking) Algorithms?
• Improved Depth First Search Algorithm to Generate Combinations of Parentheses
• Teaching Kids Programming – Back Tracking Algorithm to Generate Parentheses

–EOF (The Ultimate Computing & Technology Blog) —