首页 > 代码库 > [leetcode]Generate Parentheses
[leetcode]Generate Parentheses
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:
"((()))", "(()())", "(())()", "()(())", "()()()"
算法思路：
DFS，对每一位，尝试后缀‘（’ 或 ‘）’，用k记录左括号的个数，用couple记录成功匹配对数，注意剪枝
这个代码是我看到的几乎最简练的算法：[leetcode]Generate Parentheses
代码如下：
1 public class Solution { 2 List<String> result = new ArrayList<String>(); 3 public List<String> generateParenthesis(int n) { 4 dfs(new StringBuilder(),0,0,n); 5 return result; 6 } 7 private void dfs(StringBuilder sb,int k,int couple,int n){ 8 if(k == 0 && couple == n && sb.length() == 2 * n ){ 9 result.add(sb.toString());10 return;11 }12 if( k < 0 || sb.length() > 2 * n) return;//剪枝13 char[] c = {‘(‘,‘)‘};14 for(int i = 0; i < 2; i++){15 k = (i == 0 )? k + 1 : k-1;16 if(k > 0 && i == 1) {//配对的前提是k>0，即存在未配对的左括号17 couple++;18 k--;19 }20 if(k < 0){//如果前面木有左括号，则只能匹配右括号21 k++;22 continue;23 }24 dfs(sb.append(c[i]), k,couple, n);25 sb.deleteCharAt(sb.length() - 1);26 }27 }28 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。