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
回溯法舅逸，這里提供一個(gè)YouTubehttps://www.youtube.com/watch?v=sz1qaKt0KGQ
的鏈接支子，非常值得學(xué)習(xí)者冤，思路很清晰
這道題，給定輸入值n肮帐，需要列舉出所有 "(" 和 ")"可能的組合序列，n為()的對(duì)數(shù)，必須滿足這樣的一個(gè)約束條件关串，well-formed，即杂穷，字符串中悍缠，右括號(hào)的左側(cè)必須有一個(gè)對(duì)應(yīng)的左括號(hào)，與之閉合耐量。
那么我們最終的解決場(chǎng)景就是飞蚓，有2*n個(gè)位置，需要放置 左括號(hào) 和 右括號(hào)廊蜒，同時(shí)必須滿足 well-formed的條件趴拧，此處采用回溯法
我們?cè)诜胖?左括號(hào)時(shí)必須滿足的條件是，左括號(hào)已經(jīng)使用的數(shù)量小于總的n山叮，在放置右括號(hào)時(shí)著榴，右括號(hào)使用的數(shù)量必須小于左括號(hào)使用的數(shù)量。
那么終止條件就是 當(dāng)前字符串的位置已經(jīng)占滿了屁倔，基于這個(gè)思路脑又，可以得到上述的答案
image.png
