首页 > 代码库 > Generate Parentheses java实现

Generate Parentheses java实现

2024-07-11 07:10:37   217人阅读

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));    }}

 


联系
我们