题目:

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

这个题目应该就是用backracing,加constraint来减少搜索次数，但是由于数据比较弱，若以constraint不强也可以过了，这题其实可以更优的，这里就留给你们了，弱鸡先上代码了。

这里我就用dfs暴力就ac飘过~

import java.util.ArrayList;import java.util.List;import java.util.Stack;public class Solution {    public List
     
       generateParenthesis( int n ) {        List
      
        ret = new ArrayList
       
        ();        Node head = new Node();        makeTree( head, 0, n * 2 );        dfs( head, n * 2, new String(), ret );        return ret;    }    public void dfs( Node node, int n, String current, List
        
          ret ) {        if( node == null )            return;        if( !constraint( current ) ) return;                if( node.left != null ) {            dfs( node.left, n, current + node.left.data, ret );        }        if( node.right != null ) {            dfs( node.right, n, current + node.right.data, ret );        }        if( current.length() == n ) {            if( isValidate( current ) ) {                ret.add( current );            }        }    }            public boolean constraint(String str){        if( str.length() >= 1 && str.charAt( 0 ) == ')') return false;         return true;    }    public void makeTree( Node head, int deepth, int n ) {        if( deepth >= n )            return;        head.left = new Node( '(' );        head.right = new Node( ')' );        deepth++;        makeTree( head.left, deepth, n );        makeTree( head.right, deepth, n );    }    public boolean isValidate( String s ) {        char[] cs = s.toCharArray();        if( cs.length % 2 != 0 )            return false;        Stack
         
           stack = new Stack
          
           (); for( int i = 0; i < cs.length; i++ ) { if( cs[ i ] == '[' || cs[ i ] == '(' || cs[ i ] == '{' ) { stack.push( cs[ i ] ); } else { if( stack.isEmpty() ) return false; switch( stack.pop() ) { case '(': if( cs[ i ] != ')' ) return false; break; case '[': if( cs[ i ] != ']' ) return false; break; case '{': if( cs[ i ] != '}' ) return false; break; } } } if( !stack.isEmpty() ) return false; return true; }// public static void main( String[] args ) {// Solution s = new Solution();// List
           
             list = s.generateParenthesis( 8 );// for( String str : list ) {// System.out.println( str );// }// }}class Node { public char data; public Node left; public Node right; public Node( char data ) { this.data = data; } public Node() { }}