LeetCode刷题笔记-回溯法-括号生成

全栈程序员-用户IM • 2021年7月9日上午11:00 • 未分类

题目描述：

给出 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);

    }
}