Generate Parentheses java实现

浏览数：23 / 时间：2015年06月08日

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:

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

本题的关键在于发现规律，如下：

n=1    ()
n=2    (f(1)),f(1)+f(1)
n=3    (f(2)),f(1)+f(2),f(2)+f(1)
          。。。。

由上面的可以看出，需要计算f（n）时，需要调用f（1），f（2），。。。。，f(n-1)。

java代码实现如下：

import java.util.ArrayList;
import java.util.List;


public class Solution {
    
public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        if(n==1){                    //当n=1时，只需向里面添加一对（）即可
            list.add("()");
            
        }
        else{
                List<String> lst = generateParenthesis(n-1);    //1、首先调用f（n-1），用来计算（f（n-1））
                for(int i= 0 ; i< lst.size() ;i++){                        //当然f（n-1）有很多
                    String str = "("+lst.get(i) + ")";
                    list.add(str);
                }                
                for(int j = 1 ; j < n ;j ++){                         //2、然后将f（i）与f（n-i）进行组合
                    List<String> lst1 = generateParenthesis(j);   //依次取出f（i）里面的元素
                    List<String> lst2 = generateParenthesis(n-j);//依次取出f（n-i）里面的元素
                    for(int k = 0 ; k < lst1.size() ; k++){
                        for(int h = 0; h < lst2.size() ; h++){
                            String str = lst1.get(k) + lst2.get(h);   //将f（i）的元素与f（n-i）的元素进行组合
                            if(!list.contains(str)){
                                list.add(str);
                            }
                        }
                    }
                    
                }
        }
        return list;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println(new Solution().generateParenthesis(4));
    }

}