Algorithm Generate Parentheses
Description
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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
Submission
package com.cctoken.algorithm;
import java.util.LinkedList;
import java.util.List;
/**
* @author chenchao
*/
public class GenerateParentheses {
public List<String> generateParenthesis(int n) {
List<String> res = new LinkedList<String>();
backTracking(res, "", 0, 0, n);
return res;
}
public void backTracking(List<String> res, String solution, int leftUsed, int rightUsed, int max) {
if (solution.length() == max * 2) {
res.add(solution);
return;
}
if (leftUsed < max) {
backTracking(res, solution + "(", leftUsed + 1, rightUsed, max);
}
if (rightUsed < leftUsed) {
backTracking(res, solution + ")", leftUsed, rightUsed + 1, max);
}
}
public static void main(String[] args) {
List<String> allResults = new GenerateParentheses().generateParenthesis(3);
for (String result : allResults) {
System.out.println(result);
}
}
}
Solution
回溯法，这里提供一个YouTubehttps://www.youtube.com/watch?v=sz1qaKt0KGQ
的链接，非常值得学习，思路很清晰
这道题，给定输入值n，需要列举出所有 "(" 和 ")"可能的组合序列，n为()的对数，必须满足这样的一个约束条件，well-formed，即，字符串中，右括号的左侧必须有一个对应的左括号，与之闭合。
那么我们最终的解决场景就是，有2*n个位置，需要放置 左括号 和 右括号，同时必须满足 well-formed的条件，此处采用回溯法
我们在放置 左括号时必须满足的条件是，左括号已经使用的数量小于总的n，在放置右括号时，右括号使用的数量必须小于左括号使用的数量。
那么终止条件就是 当前字符串的位置已经占满了，基于这个思路，可以得到上述的答案
image.png
