【数据结构与算法】之深入解析“括号生成”的求解思路与算法示例
【摘要】
一、题目要求
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","(...
一、题目要求
- 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
- 示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
- 1
- 2
- 示例 2：
输入：n = 1
输出：["()"]
- 1
- 2
- 提示：1 <= n <= 8。
二、求解算法
① 暴力法
- 我们可以生成所有 22n 个 ‘(’ 和 ‘)’ 字符构成的序列，然后检查每一个是否有效即可。
- 为了生成所有序列，可以使用递归，长度为 n 的序列就是在长度为 n-1 的序列前加一个 ‘(’ 或 ‘)’。
- 为了检查序列是否有效，我们遍历这个序列，并使用一个变量 balance 表示左括号的数量减去右括号的数量。如果在遍历过程中 balance 的值小于零，或者结束时 balance 的值不为零，那么该序列就是无效的，否则它是有效的。
- Java 示例：
class Solution {
public List<String> generateParenthesis(int n) {
List<String> combinations = new ArrayList<String>();
generateAll(new char[2 * n], 0, combinations);
return combinations;
}
public void generateAll(char[] current, int pos, List<String> result) {
if (pos == current.length) {
if (valid(current)) {
result.add(new String(current));
}
} else {
current[pos] = '(';
generateAll(current, pos + 1, result);
current[pos] = ')';
generateAll(current, pos + 1, result);
}
}
public boolean valid(char[] current) {
int balance = 0;
for (char c: current) {
if (c == '(') {
++balance;
} else {
--balance;
}
if (balance < 0) {
return false;
}
}
return balance == 0;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- C++ 示例：
class Solution {
bool valid(const string& str) {
int balance = 0;
for (char c : str) {
if (c == '(') {
++balance;
} else {
--balance;
}
if (balance < 0) {
return false;
}
}
return balance == 0;
}
void generate_all(string& current, int n, vector<string>& result) {
if (n == current.size()) {
if (valid(current)) {
result.push_back(current);
}
return;
}
current += '(';
generate_all(current, n, result);
current.pop_back();
current += ')';
generate_all(current, n, result);
current.pop_back();
}
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
string current;
generate_all(current, n * 2, result);
return result;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 复杂度分析：
-
- 时间复杂度：O(22nn)，对于 22n 个序列中的每一个，用于建立和验证该序列的复杂度为 O(n)。
-
- 空间复杂度：O(n)，除了答案数组之外，所需要的空间取决于递归栈的深度，每一层递归函数需要 O(1) 的空间，最多递归 2n 层，因此空间复杂度为 O(n)。
② 回溯法
- 上面的方法还有改进的余地：可以只在序列仍然保持有效时才添加 ‘(’ or ‘)’，而不是像上面的方法那样每次添加，可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，
- 如果左括号数量不大于 n，可以放一个左括号，如果右括号数量小于左括号的数量，可以放一个右括号。
- Java 示例：
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<String>();
backtrack(ans, new StringBuilder(), 0, 0, n);
return ans;
}
public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
if (cur.length() == max * 2) {
ans.add(cur.toString());
return;
}
if (open < max) {
cur.append('(');
backtrack(ans, cur, open + 1, close, max);
cur.deleteCharAt(cur.length() - 1);
}
if (close < open) {
cur.append(')');
backtrack(ans, cur, open, close + 1, max);
cur.deleteCharAt(cur.length() - 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
- C++ 示例：
class Solution {
void backtrack(vector<string>& ans, string& cur, int open, int close, int n) {
if (cur.size() == n * 2) {
ans.push_back(cur);
return;
}
if (open < n) {
cur.push_back('(');
backtrack(ans, cur, open + 1, close, n);
cur.pop_back();
}
if (close < open) {
cur.push_back(')');
backtrack(ans, cur, open, close + 1, n);
cur.pop_back();
}
}
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
string current;
backtrack(result, current, 0, 0, n);
return result;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
③ 按括号序列的长度递归
- 任何一个括号序列都一定是由 ( 开头，并且第一个 ( 一定有一个唯一与之对应的 )。这样一来，每一个括号序列可以用 (a)b 来表示，其中 a 与 b 分别是一个合法的括号序列（可以为空）。
- 那么，要生成所有长度为 2 * n 的括号序列，定义一个函数 generate(n) 来返回所有可能的括号序列，那么在函数 generate(n) 的过程中：
-
- 需要枚举与第一个 ( 对应的 ) 的位置 2 * i + 1；
-
- 递归调用 generate(i) 即可计算 a 的所有可能性；
-
- 递归调用 generate(n - i - 1) 即可计算 b 的所有可能性；
-
- 遍历 a 与 b 的所有可能性并拼接，即可得到所有长度为 2 * n 的括号序列。
- 为了节省计算时间，我们在每次 generate(i) 函数返回之前，把返回值存储起来，下次再调用 generate(i) 时可以直接返回，不需要再递归计算。
- Java 示例：
class Solution {
ArrayList[] cache = new ArrayList[100];
public List<String> generate(int n) {
if (cache[n] != null) {
return cache[n];
}
ArrayList<String> ans = new ArrayList<String>();
if (n == 0) {
ans.add("");
} else {
for (int c = 0; c < n; ++c) {
for (String left: generate(c)) {
for (String right: generate(n - 1 - c)) {
ans.add("(" + left + ")" + right);
}
}
}
}
cache[n] = ans;
return ans;
}
public List<String> generateParenthesis(int n) {
return generate(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
- 25
- 26
- 27
- C++ 示例：
class Solution {
shared_ptr<vector<string>> cache[100] = {nullptr};
public:
shared_ptr<vector<string>> generate(int n) {
if (cache[n] != nullptr)
return cache[n];
if (n == 0) {
cache[0] = shared_ptr<vector<string>>(new vector<string>{""});
} else {
auto result = shared_ptr<vector<string>>(new vector<string>);
for (int i = 0; i != n; ++i) {
auto lefts = generate(i);
auto rights = generate(n - i - 1);
for (const string& left : *lefts)
for (const string& right : *rights)
result -> push_back("(" + left + ")" + right);
}
cache[n] = result;
}
return cache[n];
}
vector<string> generateParenthesis(int n) {
return *generate(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
- 25
④ 动态规划
- 本题最核心的思想是，考虑 i=n 时相比 n-1 组括号增加的那一组括号的位置。当我们清楚所有 i<n 时括号的可能生成排列后，对与 i=n 的情况，考虑整个括号排列中最左边的括号。
- 它一定是一个左括号，那么它可以和它对应的右括号组成一组完整的括号 “( )”，我们认为这一组是相比 n-1 增加进来的括号。那么，剩下 n-1 组括号有可能在哪呢？
- 剩下的括号要么在这一组新增的括号内部，要么在这一组新增括号的外部（右侧）。
- 既然知道了 i<n 的情况，那么就可以对所有情况进行遍历："(" + 【i=p 时所有括号的排列组合】 + “)” + 【i=q 时所有括号的排列组合】，其中 p + q = n-1，且 p q 均为非负整数。
- 事实上，当上述 p 从 0 取到 n-1，q 从 n-1 取到 0 后，所有情况就遍历完。
- 上述遍历是没有重复情况出现的，即当 (p1,q1)≠(p2,q2) 时，按上述方式取的括号组合一定不同。
- Python 示例：
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return []
total_l = []
total_l.append([None]) # 0组括号时记为None
total_l.append(["()"]) # 1组括号只有一种情况
for i in range(2,n+1): # 开始计算i组括号时的括号组合
l = []
for j in range(i): # 开始遍历 p q ，其中p+q=i-1 , j 作为索引
now_list1 = total_l[j] # p = j 时的括号组合情况
now_list2 = total_l[i-1-j] # q = (i-1) - j 时的括号组合情况
for k1 in now_list1:
for k2 in now_list2:
if k1 == None:
k1 = ""
if k2 == None:
k2 = ""
el = "(" + k1 + ")" + k2
l.append(el) # 把所有可能的情况添加到 l 中
total_l.append(l) # l这个list就是i组括号的所有情况，添加到total_l中，继续求解i=i+1的情况
return total_l[n]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
文章来源: blog.csdn.net，作者：Serendipity·y，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/Forever_wj/article/details/122587743
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）