Improved Depth First Search Algorithm to Generate Combinations of Parentheses

Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n pairs of parentheses. Note: The result set should not contain duplicated subsets.

For example, given n = 3, the result should be:

1 2 3 4 5 6 7

[   "((()))",   "(()())",   "(())()",   "()(())",   "()()()" ]

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Improved Depth First Search (or Backtracking) Algorithm to Generate Parentheses Pairs

The bruteforce – or naive Depth First Search (DFS) algorithm generates all pairs of Parentheses by trying two possibilities “(” or “)” at each position. This will take O(2^N) time. We can improve this by Adding Branching Backtracking when the current choices are invalid. For example, when we have “())*” we know it is invalid and don’t need to continue anymore.

In order to backtracking, we keep tracking the number of current opening and closing brackets. When the openning brackets are less than the closing brackets, we don’t need to continue DFS. We only continue adding the closing bracket when we have more openning brackets.

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(o, c, cur):
            nonlocal ans
            if len(cur) == n * 2:
                if o == c: # equal number of openning and closing
                    ans.append(cur)
                return
            if o >= c:
                dfs(o + 1, c, cur + "(")
                if o > c:
                    dfs(o, c + 1, cur + ")")
        dfs(0, 0, "")
        return ans

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def dfs(o, c, cur):
            nonlocal ans
            if len(cur) == n * 2:
                if o == c: # equal number of openning and closing
                    ans.append(cur)
                return
            if o >= c:
                dfs(o + 1, c, cur + "(")
                if o > c:
                    dfs(o, c + 1, cur + ")")
        dfs(0, 0, "")
        return ans

The time complexity is still exponential but is a lot faster than the naive DFS/Bruteforce algorithm.

See also: How to Generate Parentheses using Bruteforce or Depth First Search (Backtracking) Algorithms?

Also, when we have more than half opening or closing parentheses, we can abort the search as it is impossible to find a solution:

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

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def dfs(o, c, cur):
            nonlocal ans
            if len(cur) == n * 2:
                if o == c:
                    ans.append(cur)
                return
            if o > n or c > n: # <--- abort search when more than half opening/closing
                return
            if o >= c:
                dfs(o + 1, c, cur + "(")
                if o > c:
                    dfs(o, c + 1, cur + ")")
        dfs(0, 0, "")
        return ans

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def dfs(o, c, cur):
            nonlocal ans
            if len(cur) == n * 2:
                if o == c:
                    ans.append(cur)
                return
            if o > n or c > n: # <--- abort search when more than half opening/closing
                return
            if o >= c:
                dfs(o + 1, c, cur + "(")
                if o > c:
                    dfs(o, c + 1, cur + ")")
        dfs(0, 0, "")
        return ans

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) —