22. Generate Parentheses

Posted on | In | 浏览 次
Words count in article: 315 | Reading time ≈ 1

题目

  • 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
    [
        "((()))",
        "(()())",
        "(())()",
        "()(())",
        "()()()"
    ]

解题思路

  • 本题是利用溯源算法去解决的，穷举出每一种可能性，把所有成功的解都返回解空间。
    • 本题利用递归和DFS进行解决，其中重点是找到递归的传递关系，在理解递归的时候只需将其理解成一个黑盒子，考虑其中的效果
    • 递归的思路
      • 回归条件 ：当左右括号加起来等于2n的时候
      • 选择条件1：当左括号的数量小于n的时候
      • 递归关系1：左括号的数量加1
      • 选择条件2：当右括号的数量小于左括号的数量的时候
      • 递归关系2：右括号的数量加1

实现代码

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> v;
        string str = "";
        dfs(str, 0, 0, n, v);
        return v;
    }

    void dfs(string buildStr, int left, int right, int n, vector<string> &v) {
        if(left + right == 2 * n) {
            v.push_back(string(buildStr));
            return;
        }

        if(left < n) {
            dfs(buildStr + "(", left + 1, right, n, v);
        }
        
        if(right < left) {
            dfs(buildStr + ")", left, right + 1, n, v);
        }
    }
};