题目描述：
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
分析：
方法2：回溯法
1、对于每个位置都有两种选择左括号，和有括号。
2、对于每个位置都依此添加左括号，和有括号，若是不符合条件，立马停止当前分支的的继续前行。
方法1，是用的是贪心法，
1、在n=3的是在n=2的基础上，分别在左侧，右侧，外侧添加括号。
java实现
class Solution { //特此声明：我没错，辣鸡后台。我就没错！！！写此注释，以表抗议！！ public List<String> generateParenthesis2(int n) { //这是方法1,,,用的可能是贪心算法。。 List<String> list = new ArrayList<>(); if (n<1) return list; list.add("()"); if (n==1) return list; String str="()"; String s=""; for (int i=2;i<=n;i++) { int j=0; int list_len= list.size(); //先算好，别他娘的放到循环中，哼！！！！！！ int k=j; for (j = 0; j < list_len; j++) { //把list所有元素取出来，每个分别处理一遍，相对于队。 s = list.get(k); String left = "()" + s; String mid = "(" + s + ")"; String right = s + "()"; list.add(mid); list.add(left); if (!left.equals(right)) { list.add(right); } list.remove(s); } } return list; } public List<String> generateParenthesis(int n){ List<String> result=new ArrayList<>(); gen(result,"",n,n); return result; } public void gen(List<String> result,String str,int l,int r){ if (l==0 && r==0){ result.add(str); return; } if( l>r || l<0 || r<0) return ; String str2=new String(str); *****这波操作，看清楚喽，每个位置就两种情况，就不写for循环了 gen(result,str+="(",l-1,r); gen(result,str2+=")",l,r-1); } }
转载于:https://www.cnblogs.com/sqchao/p/11073479.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/100852.html原文链接：https://javaforall.net
