https://oj.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:
"((()))", "(()())", "(())()", "()(())", "()()()"
解题思路：
这题虽然是上题的延伸，但是找了半天都找不到解决思路，不会做。主要就是要列出所有的可能，不知如何解决。只能去google别人的解题思路，然后再自己去实现，大概有几种。
首先就是动态规划。定义f(n)为n对括号的所有可能性，那么他和f(i)有什么关系呢？（0<=i<n）这个思路很巧妙，或者说简单，却不容易想到。f(n)无非就是在f(n - 1)的基础上，加上一对括号。那么这个括号加在哪里，就组成了很多的可能性。
我们把左括号加在第一个位置，那么右括号加的地方，就是很多可能性。观察下面的例子。
f(0): ""
f(1): "("f(0)")"
f(2): "("f(0)")"f(1), "("f(1)")"
f(3): "("f(0)")"f(2), "("f(1)")"f(1), "("f(2)")"
f(n) = "("f(0)")"f(n-1) , "("f(1)")"f(n-2) "("f(2)")"f(n-3) ... "("f(i)")"f(n-1-i) ... "(f(n-1)")"
也就是说，f(n) = "(" + f(i) + ")" + f(n - 1 - i) (0 <= i <= n-1)
很敏感的，这和之前N个数字组成的二叉搜索树的可能性是不是很像？一个catalan数。不急，上面的思路已经足以用一个dp的方法去解决。
下面的代码是一个递归解决的例子。
public class Solution { public List<String> generateParenthesis(int n) { List<String> resultList = new ArrayList<String>(); if(n == 0){ resultList.add(""); } else if(n == 1){ resultList.add("()"); } else{ for(int i = 0; i < n; i++){ List<String> f_left = generateParenthesis(i); List<String> f_right = generateParenthesis(n - 1- i); for(String left : f_left){ for(String right : f_right){ resultList.add("(" + left + ")" + right); } } } } return resultList; } }
下面是这个dp的迭代解法。注意n的dp要声明为dp[n + 1]。
public class Solution { public List<String> generateParenthesis(int n) { List<String>[] resultLists = new ArrayList[n + 1]; resultLists[0] = new ArrayList<String>(); resultLists[0].add(""); if(n == 0){ return resultLists[0]; } resultLists[1] = new ArrayList<String>(); resultLists[1].add("()"); for(int i = 2; i <= n; i++){ resultLists[i] = new ArrayList<String>(); for(int j = 0; j < i; j++){ for(String left : resultLists[j]){ //注意，这里不是n - 1 - j for(String right : resultLists[i - 1 - j]){ resultLists[i].add("(" + left + ")" + right); } } } } return resultLists[n]; } }
除了dp外，该题还有回溯的解法，也就是普通的递归。思路是这样的，考虑构造n对括号的过程，如果左括号的数量大于右括号的数量，是可以放下右括号的，当然，这时也可以放下左括号。左括号在任何情况下都可以放下，直到没有为止（等于n）。
这里递归结束的条件自然是，左括号和右括号的数量都为n。代码如下。
public class Solution { List<String> returnList = new ArrayList<String>(); public List<String> generateParenthesis(int n) { if(n == 0){ returnList.add(""); return returnList; } backtrack("", 0, 0, n); return returnList; } public void backtrack(String result, int open, int close, int n){ if(open == n && close == n){ returnList.add(result); } if(open < n){ backtrack(result + "(", open + 1, close, n); } if(close < open){ backtrack(result + ")", open, close + 1, n); } } }
参考文章：
https://oj.leetcode.com/discuss/11509/an-iterative-method
https://oj.leetcode.com/discuss/18162/my-accepted-java-solution
https://oj.leetcode.com/discuss/25063/easy-to-understand-java-backtracking-solution
原文：http://www.cnblogs.com/NickyYe/p/4296691.html