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:"((()))", "(()())", "(())()", "()(())", "()()()" 题解： 需要用dfs －backtracking.给定的n为括号对，也就是有n个左括号和n个右括号的组合。按照顺序尝试，，直到左右括号都尝试完了，这就可以得到一个解。
注意： 左括号的数目不能大于右括号。避免“)(” 这样不合法的解出现。
/** * Generate Parantheses * * https://leetcode.com/problems/generate-parentheses/ * 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: * * "((()))", "(()())", "(())()", "()(())", "()()()" * * Tags: Backtracking. String */ import java.util.*; public class GenerateParenthesis {public static void main(String[] args) {System.out.println(generateParenthesis(3));System.out.println();System.out.println(generateParenthesis(4));}/*** Backtracking* Helper function use left and right to represent available parentheses* Initialize left as n, right as n*/public static List<String> generateParenthesis(int n) {List<String> res = new ArrayList<String>();String current = new String(); // current resultif (n <= 0) return res;dfs(res, current, n, n);return res;}/*** @param left available left parentheses* @param right available right parentheses* @param current current result* @param res the result list of the problem*/public static void dfs( List<String> res, String current, int left, int right) {if (left > right) // deal with ")("return;if (left == 0 && right == 0) {res.add( new String(current));return;}if (left > 0) dfs( res, current + "(", left-1, right); // add (, right + 1if (right > 0) dfs(res , current+ ")", left, right-1); // add ), right – 1}}
参考
“人”的结构就是相互支撑，“众”人的事业需要每个人的参与。
