首页 > 代码库 > Leetcode-Generate Parentheses
Leetcode-Generate Parentheses
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:
"((()))", "(()())", "(())()", "()(())", "()()()"
Have you met this question in a real interview?
Analysis:
We define the subproblem as if we now have n left parenthese and m right parenthese, how to generate all legal output.
1. We can always put a left parenthese, and then solve the subproblem with n-1 and m.
2. We can put a right parenthese here only if m>n, otherwise, the output violate the mathcing rule. If we put a right parenthese, we then solve the subproblem with n and m-1.
Solution:
1 public class Solution { 2 public List<String> generateParenthesis(int n) { 3 List<String> resSet = new ArrayList<String>(); 4 if (n==0) return resSet; 5 String curStr = ""; 6 parenthesisRecur(curStr,n,n,resSet); 7 return resSet; 8 } 9 10 public void parenthesisRecur(String curStr, int n, int m, List<String> resSet){11 if (n==0 && m==0){12 resSet.add(curStr);13 return;14 }15 16 if (n>0){17 curStr = curStr+"(";18 parenthesisRecur(curStr,n-1,m,resSet);19 curStr = curStr.substring(0,curStr.length()-1);20 }21 22 if (m>n){23 curStr=curStr+")";24 parenthesisRecur(curStr,n,m-1,resSet);25 curStr = curStr.substring(0,curStr.length()-1);26 }27 28 }29 }
Leetcode-Generate Parentheses
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。