難度(medium)

題目描述：

給出n對括號，請編寫一個函數來生成所有的由n對括號組成的合法組合。例如n=3，解集為：? "((()))", "(()())", "(())()", "()(())", "()()()"? 思路：

和上一道題目有點類似，但是本題可以出現(())()的組合形式，上一道題目不能是這種形式。

也就是說所有合法的括號組合不僅僅是對稱形式了，也存在非對稱形式的情況。所以用棧的思路就行不通。

但是可以觀察到，一個合法的組合，所有左括號出現的次數L=右括號出現的次數R，并且組合的長度=2*n。

所以可以擬合一個合法組合的生成過程，來進行算法的設計。

首先可以定義一個空的字符數組s，用于字符的添加，并將左括號出現的次數設為L，右括號出現的次數設為R。

那么第一次添加到括號必然是左括號‘(’，因為添加右括號不合法。因為是有多種組合，所以當左括號‘(’出現次數L小于n時，都可以一直添加，并且每添加1次，左括號出現的次數L+1，這樣看來，算法設計上就適合采用遞歸形式。如下所示：

if(L < n){    bracketArrange(n,L+1,R,s);}

(關于L < n: 因為不可能一直添加左括號，合法組合還需要右括號搭配，比如3對括號，你最多單個左括號或者=單個右括號只有3個，所以L<3，為什么不能等于3呢，因為如果if(L<=3)那么當L=3的時候仍然可以進入if語句，那么下一次L+1后，L=4就大于單個左括號的臨界值，所以不能等于3)

同理，當左括號添加完過后，就可以添加右括號了，添加的條件肯定是先有左括號的存在，并且左括號的個數L要大于右括號的次數R(設想，當你左括號2個右括號3個了，(())) 、())()....肯定不合法的，其次右括號個數還要小于n，上面已經說了原因。那么遞歸形式：

if(R < L && R < n){  bracketArrange(n,L,R+1,s)}

當左右括號添加完畢后，找一個list存儲，那么此時整個字符組合的長度=2*n，并且結束遞歸，這樣這個條件便是遞歸出口：

if(s.length() == 2 * n){??list.add(s);    return;}

講道理，整個代碼部分，return才是最巧妙靈性的設計，有了return,才有了這么多不重復的合法組合。因為第一種組合走完，return會返回到上一個遞歸，上一個遞歸又會返回給上上個遞歸，然后在條件合適的if語句下面做第二次組合。這里不是很好表述，需要自己debug跑一下，就大概清楚了。

代碼：

import java.util.ArrayList;public class myBracketArrange {    static ArrayListlist = new ArrayList<>();    public static void main(String[] args) {????????Scanner in = new Scanner(System.in);????????int n = in.nextInt();????????bracketArrange(n,0,0,"");        for (int i = 0; i < list.size(); i++) {            System.out.print(list.get(i));            System.out.println("\t");        }    }    public static void bracketArrange(int n, int l, int r, String s){        if (l < n){            bracketArrange(n,l+1, r, s + '(');        }        if (r < l && r < n){            bracketArrange(n, l,r+1,s + ')');        }        if(s.length() == 2*n){            list.add(s);            return;        }    }}

想寫點其他東西了...

再看吧。

封面和配圖來自于網絡，侵刪