interviewalgo
, , , ,
Source
Edit
History

22. 括号生成

Introduction

Question：22. 括号生成

解法一

Analysis

虽说是回溯的题目，但是看着感觉像是动态规划的题目。

大概的动态规划方程为：

  • F(n) = \sum_{1<=i<=n-1} join(F(i),F(n-i)) + '('F(n-1)')'
  • F(1) = {'()'}

感觉比较难用公式描述，但是写起来倒是挺简单的。

Implement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<vector<string>> res{{},{"()"}};
vector<string> generateParenthesis(int n) {
    if (n < res.size()) return res[n];

    for(int i = 2;i <= n;i++) {
        unordered_set<string> iset;
        for(auto &s: res[i-1]) {
            iset.insert("(" + s + ")");
        }
        for(int j = i - 1;j >= 1;j--) {
            for(auto &s1: res[j]) {
                for(auto &s2: res[i - j]) {
                    iset.insert(s1+s2);
                }
            }
        }

        res.push_back({iset.begin(), iset.end()});    
    }
    return res[n];
}

解法二

Analysis

竟然是回溯的问题，那就用回溯解决一下吧。

简单来说就是构造一个用n个左括号和n个右括号来构造一个有效的括号组合。由于解的长度一定是2n，我们可以在回溯的每一层都为字符串添加一个(或者)。而剪纸的条件也不会很复杂：

  • 插入的(和)个数不能超过n
  • 插入的(的个数一定大于插入的)个数

Implement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<string> generateParenthesis(int n) {
    vector<string> res;
    string s;
    func(res, s, n, n);
    return res;
}
void func(vector<string> &res, string &s, int left, int right) {
    if (left == 0 && right == 0) {
        res.push_back(s);
        return;
    }
    if (left > right) return;
    if (left != 0) {
        s.push_back('(');
        func(res, s, left - 1, right);
        s.pop_back();
    }
    s.push_back(')');
    func(res, s, left, right - 1);
    s.pop_back();
}

One More Thing

  • 一般这种要求不返回重复的，都可以用set或者unordered_set来暴力解决。