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:
"((()))", "(()())", "(())()", "()(())", "()()()"
解题思路一：
通过观察n=2和n=3的情况可以知道，只要在n=2的String 开头、末尾、'(' 插入“（）”即可，注意防止重复。
JAVA实现如下：
static public List<String> generateParenthesis(int n) {
HashSet<String> set = new HashSet<String>();
if (n == 1)
set.add("()");
if (n > 1) {
ArrayList<String> lastList = new ArrayList<String>(
generateParenthesis(n - 1));
StringBuilder sb = new StringBuilder();
for (String string : lastList) {
sb = new StringBuilder(string);
set.add(sb.toString() + "()");
set.add("()" + sb.toString());
for (int i = 0; i < sb.length() - 1; i++) {
if (sb.charAt(i) == '(') {
sb.insert(i + 1, "()");
set.add(sb.toString());
}
sb = new StringBuilder(string);
}
}
}
return new ArrayList<String>(set);
}
解题思路二：
通过观察可以发现，任何符合条件的Parenthesis(n)总是可以分解为(generateParenthesis(k))+generateParenthesis(n-1-k)，同时由于后半部分generateParenthesis(n-1-k)的唯一性，这种算法不会产生重复的元素，因此采用DFS进行一次遍历即可，这种算法更高效！JAVA实现如下：
static public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<String>(), leftList, rightList;
if (n == 0)
list.add("");// 很关键，不能删除
if (n == 1)
list.add("()");
else {
for (int i = 0; i < n; i++) {
leftList = generateParenthesis(i);
rightList = generateParenthesis(n - i - 1);
for (String leftPart:leftList)
for (String rightPart:rightList)
list.add("(" + leftPart + ")" + rightPart);
}
}
return list;
}
C++：
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string>res;
if (n == ) {
res.push_back("");
return res;
}
if (n == ) {
res.push_back("()");
return res;
}
for (int i = ; i < n; i++) {
vector<string> left = generateParenthesis(i);
vector<string>right = generateParenthesis(n-i-);
for (string leftPart : left)
for (string rightPart : right)
res.push_back("(" + leftPart + ")" + rightPart);
}
return res;
}
};