已知n組括號，開發一個程序，生成這n組括號所有的合法的組合可能。 例如:n = 3
結果為: ["((()))", “(()())”, “(())()”, “()(())”, “()()()”]

首先思考如何生成所有的括號組合的可能性，即例如2組括號，總共4個符號組合的可能型，那么每個位置就有兩種括號的可能性，要么左括號，要么右括號，此時可以寫出如代碼：

void generate(string item, int n, std::vector<string> &result) {if (item.size() == 2 * n) {result.push_back(item);return ;}generate(item + "(", n , result);generate(item + ")", n , result);
} std::vector<string> generate_parenthesed(int n) {std::vector<string> result;generate("", n, result);return result;
}

測試如上代碼,可以看到2組括號總共可能有16中組合的可能性:

2
((((
((()
(()(
(())
()((
()()
())(
()))
)(((
)(()
)()(
)())
))((
))()
)))(
))))

但是根據輸出結果，我們顯然能夠看出來很多結果并不符合 合法括號的要求，那么什么是合法的括號呢？或者說如何生成一個合法的括號呢？

根據括號的規律：

1. 初始括號一定是左括號
2. 括號集中左括號的數目一定和右括號的數目相等
3. 添加括號的過程中如果左括號的數目大于右括號，則才能夠添加右括號，否則不能添加右括號

基于以上過程，實現如下:

/*left和right代表剩余括號數，left代表還剩下多少個左括號未添加，right代表還剩下多少個右括號未添加*/
void generate_leagal(string item, int left, int right, std::vector<string> &result) {if(left == 0 && right == 0) {result.push_back(item);return;}if(left > 0) { //當還有剩余的左括號未添加，則添加左括號generate_leagal(item + "(", left - 1, right, result);}if (left < right) { //當已添加的左括號的數目大于右括號，則才能夠添加右括號generate_leagal(item + ")", left, right - 1, result);}
}std::vector<string> generate_parenthesed(int n) {std::vector<string> result;generate_leagal("", n, n, result);return result;
}

測試代碼如下:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>/*
已知n組括號，開發一個程序，生成這n組括號所有的合法的組合可能。 例如:n = 3
結果為: ["((()))", "(()())", "(())()", "()(())", "()()()"]
*/using namespace std;void generate_leagal(string item, int left, int right, std::vector<string> &result) {if(left == 0 && right == 0) {result.push_back(item);return;}if(left > 0) {generate_leagal(item + "(", left - 1, right, result);}if (left < right) {generate_leagal(item + ")", left, right - 1, result);}
}std::vector<string> generate_parenthesed(int n) {std::vector<string> result;generate_leagal("", n, n, result);return result;
}int main(int argc, char const *argv[])
{int n;std::vector<string> result;cin >> n;result = generate_parenthesed(n);for (int i = 0;i < result.size(); ++i) {cout << result[i] << endl;}return 0;
}

輸出如下:

#輸入
4
#輸出
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

總結

以上是生活随笔為你收集整理的递归/回溯：Generate Parentheses生成合法括号的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。