【leetcode】22. Generate Parentheses

题目描述：

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

解题分析：

这类题一般都要用递归的方法来解决。需要设两个集合类分别存储待匹配的（，）的个数。

这里需要明白一点：当待匹配的（的个数永远不小于待匹配的）的个数时只能匹配（，否则会导致错误。（可以自己在纸上试一下就好理解了），其余情况可以考虑匹配（和）两种情况下可能的结果。

具体代码：

 public class Solution {

     public static List<String> generateParenthesis(int n){

         List<String> result = new ArrayList<String>();

         List<Character> array1=new LinkedList<Character>();

         List<Character> array2=new LinkedList<Character>();

         char[] array = new char[2*n];

         for(int i=0;i<n;i++){

             array1.add('(');

             array2.add(')');

         }

         fun1(array1,array2,result,array,0);

         return result;

     }

     public static void fun1(List<Character> array1,List<Character> array2,List<String> result,char[] array,int index){

         if(index==array.length-1){

             if(array1.size()==0&&array2.size()==1){

                 array[index]=array2.remove(0);

                 result.add(new String(array));

                 array[index]=' ';

                 array2.add(')');

                 return;

             }

             else{

                 return;

             }

         }

         //只能填'('

         if(array1.size()>=array2.size()){

             array[index]=array1.remove(0);

             fun1(array1,array2,result,array,index+1);

             array[index]=' ';

             array1.add('(');

         }

         else{

             //先试'('

             if(array1.size()>0){

                 array[index]=array1.remove(0);

                 fun1(array1,array2,result,array,index+1);

                 array[index]=' ';

                 array1.add('(');

             }

             //再试')'

             array[index]=array2.remove(0);

             fun1(array1,array2,result,array,index+1);

             array[index]=' ';

             array2.add(')');

         }

     }

 }

巴特西

【leetcode】22. Generate Parentheses

最新文章

热门文章