记一次转不过弯的递归

 2023-09-05 阅读 744 评论 0

摘要:leetCode原题: Givennpairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, givenn= 3, a solution set is: "((()))", "(()())", "(())()", "()(())", "()()()&#

leetCode原题:

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、有左括号必定先写左括号,再添右括号

2、当无左括号时,只要右括号数小于左括号数,就可以舔右括号

 

一开始想到了stack,后来发现递归更容易记录结果。

递归如下:


private static void combination(List<String> result, int left, int right, String str) {

if(left ==0 && right == 0) {
result.add(str);
}
if(left > 0){
combination(result, left-1, right, str+"(");
}
if(right > 0&& right > left) {
combination(result, left, right-1, str+")");
}
}


 

转载于:https://www.cnblogs.com/wazqy/p/7831596.html

版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。

原文链接:https://hbdhgg.com/1/223.html

发表评论:

本站为非赢利网站,部分文章来源或改编自互联网及其他公众平台,主要目的在于分享信息,版权归原作者所有,内容仅供读者参考,如有侵权请联系我们删除!

Copyright © 2022 匯編語言學習筆記 Inc. 保留所有权利。

底部版权信息