How to Generate Parentheses using Bruteforce or Depth First Sear

  • 时间：2020-09-23 15:11:59
  • 分类：网络文摘
  • 阅读：103 次

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

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
难忘七月之青塘小学实践　 数正方形个数的数学题：5X5方格共有36个格点　 数学题：小兔晴天可以采12个蘑菇　 数学题：老师说我像你这么大的时候你才刚刚1岁　 数学题：甲、丙两组人比乙组人数多2倍还多2人　 数学题：22名家长和老师陪同学生参加某次数学竞赛　 数学题：求X的长度是多少厘米　 正好可以把它平均切成2个相等的正方体　 数学题：求三角形ABC中阴影正方形的边长是多少厘米　 数学题：三角形ABF的面积比三角形CEF的面积大8平方厘米　
评论列表
添加评论