Home
How to Generate Parentheses using Bruteforce or Depth First Search (Backtracking) Algorithms?
Tags:, , , , , ,

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

July 24, 2019 No Comments algorithms, brute force, c / c++, DFS, python, recursive, string

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is:

1
2
3
4
5
6
7

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

We can use the following two algorithms: bruteforce, or backtracking/Depth First Search Algorithm to generate n pairs of valid Parentheses. We can use recursion to implement both algorithms as the follows.

Bruteforce Algorithm to Generate Parentheses

First, we can check if a given string is a valid Parentheses. If we meet a ‘(‘ we increment the balance and ‘)’ we decrement it. At any time, if the balance is negative, it is invalid. Finally a valid Parentheses should have zero balance at the end.

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

bool isValidParentheses(const string &s) {
    int balance = 0;
    for (int i = 0; i < s.size(); ++ i) {
        if (s[i] == '(') {
            balance ++;
        } else {
            balance --;
            if (balance < 0) {
                return false;
            }
        }
    }
    return balance == 0;
}
bool isValidParentheses(const string &s) {
    int balance = 0;
    for (int i = 0; i < s.size(); ++ i) {
        if (s[i] == '(') {
            balance ++;
        } else {
            balance --;
            if (balance < 0) {
                return false;
            }
        }
    }
    return balance == 0;
}

Then, we can use the recursion to bruteforce all the possible strings and check one-by-one if it is a valid using isValidParentheses method. As each character has two possibilities, and there are N*2 characters, there will be O(2^(2N)) time complexity, and over-all algorithm complexity will be O(n*2^(2N)) including the isValidParentheses which takes O(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

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> r;        
        string cur(n * 2, ' ');
        dfs(r, cur, 0);
        return r;
    }
    
private:
    void dfs(vector<string> &res, string &cur, int pos) {
        if (pos == cur.size()) {
            if (isValidParentheses(cur)) {
                res.push_back(cur);
            }
        } else {
            cur[pos] = '(';
            dfs(res, cur, pos + 1);
            cur[pos] = ')';
            dfs(res, cur, pos + 1);
        }
        
    }
};
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> r;        
        string cur(n * 2, ' ');
        dfs(r, cur, 0);
        return r;
    }
    
private:
    void dfs(vector<string> &res, string &cur, int pos) {
        if (pos == cur.size()) {
            if (isValidParentheses(cur)) {
                res.push_back(cur);
            }
        } else {
            cur[pos] = '(';
            dfs(res, cur, pos + 1);
            cur[pos] = ')';
            dfs(res, cur, pos + 1);
        }
        
    }
};

Backtracking/DFS Algorithm to Generate Parentheses

Apparently, the performance of the bruteforce algorithm is not ideal as we don’t need to generate the invalid Parentheses in the first place. We can use two counters to remember the number of opening and closed Parentheses respectively, and only backtracking those valid branches. The invalid branches are cut-off and abandoned. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> r;        
        dfs(r, 0, 0, n, "");
        return r;
    }
    
private:
    void dfs(vector<string> &res, int open, int close, int n, string cur) {
        if (cur.size() == 2 * n) {
            res.push_back(cur);
            return;
        }
        if (open < n) {
            dfs(res, open + 1, close, n, cur + "(");
        }
        if (close < open) { // the close Parentheses should be less than the opening Parentheses
            dfs(res, open, close + 1, n, cur + ")");
        }
    }
};
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> r;        
        dfs(r, 0, 0, n, "");
        return r;
    }
    
private:
    void dfs(vector<string> &res, int open, int close, int n, string cur) {
        if (cur.size() == 2 * n) {
            res.push_back(cur);
            return;
        }
        if (open < n) {
            dfs(res, open + 1, close, n, cur + "(");
        }
        if (close < open) { // the close Parentheses should be less than the opening Parentheses
            dfs(res, open, close + 1, n, cur + ")");
        }
    }
};

The total number of different Parentheses is the n-th Catalan number, which is 1/(n+1)C(2n, n) and the complexity is bounded asymptotically to 4^n/(n*sqrt(n)).

The same algorithm implemented in Python, as follows:

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

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        arr = []
        def dfs(open, close, n, cur):            
            nonlocal arr
            if len(cur) == 2 * n:
                arr.append(cur)
                return            
            if open < n:
                dfs(open + 1, close, n, cur + '(')
            if close < open:
                dfs(open, close + 1, n, cur + ')')            
        dfs(0, 0, n, '')
        return arr
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        arr = []
        def dfs(open, close, n, cur):            
            nonlocal arr
            if len(cur) == 2 * n:
                arr.append(cur)
                return            
            if open < n:
                dfs(open + 1, close, n, cur + '(')
            if close < open:
                dfs(open, close + 1, n, cur + ')')            
        dfs(0, 0, n, '')
        return arr

Generate Parentheses Algorithms:

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
680 words
Last Post: Algorithm to Construct Binary Tree from Preorder and Inorder Traversal
Next Post: String Algorithm: Reverse the first k characters for every 2k characters

The Permanent URL is: How to Generate Parentheses using Bruteforce or Depth First Search (Backtracking) Algorithms?

Related posts:

  1. Bruteforce or Line Sweep Algorithms to Remove Covered Intervals Given a list of intervals, remove all intervals that are covered by another interval in...
  2. C++ Chess Board Printing in Windows Using CodePage 437 – Extended ASCII Well, most people, when they start programming in C/C++, they would like to print something...
  3. Teaching Kids Programming – The Left Side View of Binary Tree via Breadth First Search Algorithm Teaching Kids Programming: Videos on Data Structures and Algorithms Given a binary tree root, return...
  4. GoLang: Implement Trie (Prefix Tree) Trie aka Prefix Tree is a data structure helps to search a word or prefix...
  5. C++ Coding Reference: is_sorted_until() and is_sorted() We talked about sorting (unstable and stable) algorithms implemented in C++ STL. The STL algorithm...
  6. Breadth-First Search Algorithm to Solve Puzzle (Rotting Oranges) in a Grid In a given grid, each cell can have one of three values: the value 0...
  7. Using BackTracking Algorithm to Find the Combination Integer Sum Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find...
  8. Intersection of Three Sorted Arrays using Three Pointers Given three integer arrays arr1, arr2 and arr3 sorted in strictly increasing order, return a...

Leave a Reply