括号生成__牛客网

Java

月亮邮递员3

import java.util.*;

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* @param n int整型

* @return string字符串ArrayList

*/

public ArrayList<String> generateParenthesis(int n) {

// write code here

ArrayList<String> arr = new ArrayList<>();

backtrack(arr, "", 0, 0, n);

return arr;

}

private void backtrack(ArrayList<String> arr, String s, int left, int right,

int n) {

if (left == n && right == n) {

arr.add(s);

return;

} else

if (right > left) {

return;

}

// 这个(是parent.下面是child,相当于他的两个分支.

if (left < n) {

backtrack(arr, s + "(", left + 1, right, n);

}

if (right < n) {

backtrack(arr, s + ")", left, right + 1, n);

}

1. 依靠左边括号和右边括号的数量的进行判断.
2.

if (left < n) {

backtrack(arr, s + "(", left + 1, right, n);

}

if (right < n) {

backtrack(arr, s + ")", left, right + 1, n);

}
这两个是root是child.

发表于 2024-11-21 17:09:18 回复(0)

Java

牛客839384289号

ArrayList<String> list=new ArrayList<>();
public ArrayList<String> generateParenthesis (int n) {
    // write code here
    dfs(new StringBuilder() ,n ,n);
    return list;
}

public void dfs(StringBuilder sb ,int left ,int right){
    if(left==0 && right==0){
        list.add(sb.toString());
    }
    if(left>0){
        sb.append('(');
        dfs(sb ,left-1 ,right);
        sb.deleteCharAt(sb.length()-1);
    }
    if(right>left){
        sb.append(')');
        dfs(sb ,left ,right-1);
        sb.deleteCharAt(sb.length()-1);
    }
}

发表于 2024-09-22 16:16:56 回复(0)

Java

人间水长东

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        ArrayList<String> result = new ArrayList<>();
        process (result, "", 0, 0, n);
        return result;
    }

    public void process (ArrayList<String> result, String cur, int left, int right, int max) {
        // 递归出口，当左括号与右括号数量相等且都为给定值时退出递归
        if (left == right && right == max) {
            result.add(cur);
            return;
        }
        // 情况1：数量未达到上限时，可以加一个(
        if (left < max) {
            process(result, cur + '(', left + 1, right, max);
        }
        // 情况2：数量未达到(的数量时，可以加一个)
        if (right < left) {
            process(result, cur + ')', left, right + 1, max);
        }
    }
}

发表于 2024-08-17 12:23:36 回复(0)

Java

Andy_Yang

一种迭代状态的写法：

import java.util.*;

public class Solution {
    public ArrayList<String> generateParenthesis (int n) {
        // 长度为2n，每位上两个状态    ( = 0    )  = 1     枚举所有可能的状态，找出满足条件的状态对应成括号
        // 1.状态中 0 和 1 数量相同
        // 2.不存在右括号数量比左括号数量多的前缀
        int m = n << 1, l = 0;  // 待匹配左括号的数量
        char[] s = new char[m];
        ArrayList<String> res = new ArrayList<>();
        for (int i = 0; i < (1 << m); i++) {
            l = 0;
            for (int j = 0; j < m; j++) {
                if ( (i >> j & 1) == 0 ) { l++; s[j] = '('; }
                else {
                    // 直接消掉一个左括号，不用单独统计右括号数量
                    l--;
                    // 说明右括号比之前的左括号多了，该状态无效
                    if (l < 0) break;
                    s[j] = ')';
                }
            }
            // 说明状态的左右括号数量相同，且没有出现一个右括号数量比左括号数量多的前缀  为有效状态
            if (l == 0) {
                res.add(new String(s));
            }
        }
        return res;
    }
}

发表于 2024-07-25 14:55:33 回复(0)

Java

做则必成的勇气和信心

 public ArrayList<String> generateParenthesis (int n) {
        ArrayList<String> ans=new ArrayList<>();
        build("",0,0,n,ans);
        return ans;
    }
    public void build(String str,int left,int right,int n,ArrayList<String> ans){
        //截至条件
        if(left==n&&right==n){//左右括号都用完了
            ans.add(str);
        }
        if(left<right){//先走的left只可能大于等于right ，这里剪枝
            return;
        }
        if(left<n){//先左括号
            build(str+"(",left+1,right,n,ans);
        }
        if(right<n){
            build(str+")",left,right+1,n,ans);
        }
    }

发表于 2023-07-15 11:51:52 回复(0)

Java

BlueProtocol

public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        // write code here
        ArrayList<String> list = new ArrayList<>();
        recurse(0, 0, new String(), list, n);
        return list;
    }

    public void recurse(int left, int right, String str, ArrayList<String> list,
                        int n) {
        if (left == n && right == n) {
            list.add(str);
            return;
        }
        // 进一次左括号
        if (left < n ) {
            recurse(left + 1, right, str + "(", list, n);
        }

        // 进一次右括号
        if (right < n && left > right) {
            recurse(left, right + 1, str + ")", list, n);
        }
    }

}

发表于 2023-03-21 14:42:20 回复(0)

Java

wpcAlex

import java.util.*;


public class Solution {
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        ArrayList<String> res = new ArrayList<String>();
        StringBuilder sb = new StringBuilder();
        recursion(res, sb, 0, 0, n);
        return res;
    }
    private void recursion(ArrayList<String> res, StringBuilder sb, int left,
                           int right, int n) {
        if(sb.length() == 2 * n){//左右括号都用完了，就加入结果
            res.add(new String(sb));
            return;
        }          
        if(left < n){//使用一次左括号
            sb.append('(');
            recursion(res, sb, left + 1, right, n);
            sb.deleteCharAt(sb.length() - 1);//回溯
        }  
        if(right < n && right < left){//使用右括号个数必须少于左括号
            sb.append(')');
            recursion(res, sb, left, right  + 1, n);
            sb.deleteCharAt(sb.length() - 1);
        }          
    }
}

发表于 2022-12-29 09:58:20 回复(0)

Java

快乐的猕猴桃反对画饼

import java.util.*;


public class Solution {
    /**
     *
     * @param n int整型
     * @return string字符串ArrayList
     */
    ArrayList<String> ans = new ArrayList<String>();
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        //构造括号数组=选择列表
        char[] s = new char[2 * n];
        for (int i = 0; i < 2 * n; i++) {
            if (i < n)
                s[i] = '(';
            else
                s[i] = ')';
        }
        //选择路径
        StringBuilder sb = new StringBuilder();
        //visit列表
        boolean vis[] = new boolean[2 * n];
        dfs(s, vis, sb);//深搜
        return ans;
    }
    void dfs(char[] s, boolean vis[], StringBuilder sb) {
        if (sb.length() == s.length) {
            ans.add(sb.toString());
            return;
        }
        for (int i = 0; i < s.length; i++) {
            if (vis[i])
                continue;
            //判断合法性
            if (!legal(sb, s[i]))
                continue;
            //去除重复项
            if(i!=0&&s[i-1]==s[i]&&!vis[i-1])
                continue;
            //dfs+回溯
            vis[i] = true;
            sb.append(s[i]);
            dfs(s, vis, sb);
            vis[i] = false;
            sb.deleteCharAt(sb.length() - 1);
        }

    }
    boolean legal(StringBuilder sb, char t) {
        //左括号直接true
        //右括号则判断 左右括号数量关系
        if (t == '(')  return true;
        if (sb.length() == 0 && t == ')')  return false;
        int left=0,right=0;
        for(int i=0;i<sb.length();i++){
            if(sb.charAt(i)=='(')
                left++;
            else if(sb.charAt(i)==')')
                right++;
        }
        if(left>right)
            return true;
        return false;
    }
}

发表于 2022-12-01 23:48:56 回复(0)

Java

牛客375488447号

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    ArrayList<String> list = new ArrayList<>();
    public ArrayList<String> generateParenthesis (int n) {
        // 操！！ 越做越沙雕  我感觉我要是不推理一下  我真做不出来
        // 还是一个排列问题  不过每次排列 左括号要比右括号少才行
        // write code here
        join(n,n,new StringBuilder());
        return list;

    }

    public void join(int left,int right, StringBuilder s){
        if(left == 0 && right == 0){
            list.add(s.toString());
            return;
        }
        // 第一次进来肯定是左括号先手
        if(left > 0){
            s.append("(");
            join(left - 1, right,s);
            s.deleteCharAt(s.length() - 1);
        }
        // 右括号不仅要大于零  还需要比左括号多  不然后续输出的括号对应不上
        // 模拟一下   假设现在 n=3
        // 第一次排列结果应该是  ((()))
        // 此时return  回溯   这时返回的上一步是在下面的方法里面
        // 依次回溯到 (((  这种  就会跳到左括号里面的join执行完之后 继续删
        // 就会变为 (( 此时上面判断走完了  就会走到下面  条件成立
        // 此时就会变为 (()  递归变为  (()())   这就是第二次的结果
        // 以此类推  第三次  (())()  第四次本会成为  (()))(   但是这种不成立  判断不通过
        // 第四次应改为  ()(())   第五次   ()()() 到此时  已经没有了
        if(right > 0 && left < right){
            s.append(")");
            join(left,right - 1,s);
            s.deleteCharAt(s.length() - 1);
        }
    }
}

发表于 2022-11-11 09:45:33 回复(0)

Java

不会起名就这样吧

如果tmp长度等于n*2，说明合法的把括号取完了，将tmp存入list，如果n < 0 || m < 0超限直接返回，n > m剩的左括号多，说明进去的右括号多，右括号多与左括号不合法，返回上层，如果等于，只能存入左括号，如果小于则都可以存，但要注意存那个括号要注意那个括号是否还有剩余，有才能存入

public ArrayList<String> generateParenthesis (int n) {
        ArrayList<String> list = new ArrayList<>();
        if (n == 0) {
            return list;
        }
        StringBuffer tmp = new StringBuffer();
        generate(2*n,n, n, list, tmp);
        return list;
    }
    public void generate(int count,int n, int m, ArrayList<String>list, StringBuffer tmp) {
        if (tmp.length() == count) {
            list.add(new String(tmp));
            return;
        }
        if (n < 0 || m < 0) {
            return;
        }
        if (n > m) {
            return;
        }
        if (n == m) {
            tmp.append("(");
            generate(count,n-1, m , list, tmp);
            tmp.deleteCharAt(tmp.length()-1);
        } else if (m > n) {
            if(n>0){
                tmp.append("(");
                generate(count,n-1, m , list, tmp);
                tmp.deleteCharAt(tmp.length()-1);
            }
           if(m>0) {
               tmp.append(")");
               generate(count, n, m - 1, list, tmp);
               tmp.deleteCharAt(tmp.length() - 1);
           }
        }
    }

发表于 2022-10-24 12:57:18 回复(0)

Java

只一眼

    // 没有想到这就写出来了，虽然和答案不太一样，答案是有n个左括号和右括号，然后使用的方式
    // 我用的是每一轮加一对括号，遍历上一轮的所有左括号
    public static ArrayList<String> generateParenthesis(int n) {
        // write code here
        StringBuilder builder = new StringBuilder();
        Set<String> res = new HashSet<>();
        recursion(n, 0, builder, res);
        return new ArrayList<String>(res);
    }

    // "((()))", "(()())", "(())()", "()()()", "()(())"
    // "(())","()()"
    public static void recursion(int n, int index, StringBuilder builder, Set<String> res) {
        // 遍历结束
        if (index == n) {
            res.add(builder.toString());
            return;
        }

        for (int i = 0; i < builder.length(); i++) {
            // 遇到左括号，就往后面加一个()，然后进入下一个
            if (builder.charAt(i) == '(') {
                builder.insert(i + 1, "()");
                recursion(n, index + 1, builder, res);
                // 回溯
                builder.deleteCharAt(i + 1);
                builder.deleteCharAt(i + 1);
            }
        }
        // 结尾的时候再加一个
        builder.append("()");
        recursion(n, index + 1, builder, res);
        builder.deleteCharAt(builder.length() - 1);
        builder.deleteCharAt(builder.length() - 1);
    }

发表于 2022-10-06 16:42:28 回复(0)

Java

勇敢牛牛不怕难

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    ArrayList<String>  res=new ArrayList<>();
    int left;
    int right;
    int len;
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        left=n;
        right=n;
        len=2*n;
        count(new StringBuilder(),0,0);
        
        return res;
    }
    
    //第三个参数表示使用左括号的数量
    public void count(StringBuilder log,int index,int useleft){
        if(index>=len){
            res.add(log.toString());
            return;
        }
        if(left>0){
            left--;
            log.append('(');
            count(log,index+1,useleft+1);
            
            log.deleteCharAt(log.length()-1);
            left++;
        }
        //左括号useleft使用数量要大于0才行，否则是非法的组合
        if(right>0&&useleft>0){
            right--;
            log.append(')');
            count(log,index+1,useleft-1);
            
            log.deleteCharAt(log.length()-1);
            right++;
            
        }
        
    }
}

发表于 2022-08-29 18:35:35 回复(0)

Java

咖啡滑滑子

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    ArrayList<String> res = new ArrayList<>();
    StringBuilder temp = new StringBuilder();
    public void kuohuao(int left,int right,int n){
        if(left == n && right == n){
            res.add(new String(temp));
                return ;
        }
        if(left < n ){
            temp.append("(");
            kuohuao(left+1,right,n);
            //用全局StringBuilder需要回溯 || 如果是参数传递到每一层则不需要回溯如官答
            temp.deleteCharAt(temp.length()-1);
        }
        if(left > right && right < n){
            temp.append(")");
            kuohuao(left,right+1,n);
            //用全局StringBuilder需要回溯 || || 如果是参数传递到每一层则不需要回溯如官答
            temp.deleteCharAt(temp.length()-1);
        }
    }
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        kuohuao(0,0,n);
        return res;
    }
}

发表于 2022-08-13 10:36:51 回复(0)

Java

牛客用户007

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return string字符串ArrayList
     */
    ArrayList<String> res = new ArrayList<String>();
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        String sb = "";
        generate(sb, 0, 0, n);
        return res;
    }

    public void generate(String sb, int left, int right, int n) {
        if (left == n && right == n) {
            res.add(sb);
        }

        if (left < n) {
            generate(sb + "(", left + 1, right, n);
        }
        if (right < left && right < n) {
            generate(sb + ")", left, right + 1, n);
        }
    }
}

发表于 2022-08-09 15:11:17 回复(0)

Java

lizi-hust

import java.util.*;
public class Solution {
    ArrayList<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    
    public ArrayList<String> generateParenthesis (int n) {
        backtrack(n, n);
        return res;
    }
    
    public void backtrack(int left, int right){
        if(left<0 || right<0) return;
        if(left > right) return;
        if(left==0 && right==0){
            if(!res.contains(new String(sb))) res.add(new String(sb));
            return;
        }
        sb.append('(');
        backtrack(left-1, right);
        sb.deleteCharAt(sb.length()-1);
        
        sb.append(')');
        backtrack(left, right-1);
        sb.deleteCharAt(sb.length()-1);
    }
}

发表于 2022-07-19 17:34:56 回复(0)

Java

东南吴彦祖

递归：

public class Solution {

    private ArrayList<String> ans = new ArrayList<>();
    public ArrayList<String> generateParenthesis (int n) {
        dfs(n-1,n,"(");
        return ans;
    }

    public void dfs(int m,int n,String t){
        if(n < m || m < 0 || n < 0) return ;
        if(n == 0 && m == 0){
            ans.add(t);
        }
        dfs(m-1,n,t+"(");
        dfs(m,n-1,t+")");
    }
}

发表于 2022-07-03 14:25:54 回复(0)

Java

牛客475836892号

全是递归，写个回溯

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    ArrayList<String> res = new ArrayList<>();
    StringBuilder builder = new StringBuilder();

    public ArrayList<String> generateParenthesis(int n) {
        backtracking(n, 0, 0);
        return res;
    }

    public void backtracking(int n, int left, int right) {
        if (right > left) return;
        if (builder.length() == 2 * n) {
            if (left == n && right == n) res.add(builder.toString());
            return;
        }
        builder.append("(");
        backtracking(n, left + 1, right);
        builder.deleteCharAt(builder.length() - 1);
        builder.append(")");
        backtracking(n, left, right + 1);
        builder.deleteCharAt(builder.length() - 1);
    }
}

发表于 2022-06-07 20:01:39 回复(0)

Java

千楼

import java.util.*;


public class Solution {
    /**
     *
     * @param n int整型
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        ArrayList<String> res = new ArrayList<>();
        parenthesis(0, 0, n, "", res);
        return res;
    }
    private void parenthesis(int left, int right, int n, String str,
                             ArrayList<String> res) {
        if (left == n && right == n) {
            res.add(str);
            return;
        }
        if (left < n) {
            parenthesis(left + 1, right, n, str + "(", res);
        }
        if (left > right) {
            parenthesis(left, right + 1, n, str + ")", res);
        }
    }
}

发表于 2022-04-10 15:22:14 回复(0)

Java

我是小韩

暴力算法：DFS + 回溯

第一种做法：先添加（，在添加），如下所示

import java.util.*;


public class Solution {
    /**
     * 设置结果
     */
    public static ArrayList<String> result = new ArrayList<>();
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        dfs(n, 0 ,0, new StringBuilder());
        return result;

    }
 public void dfs(int n, int left, int right, StringBuilder stringBuilder) {
        // 结束条件
        if (stringBuilder.length() == 2 * n) {
            result.add(stringBuilder.toString());
            return;
        }
        if (left < n) {
            // 添加（
            dfs(n, left + 1, right, stringBuilder.append('('));
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }
        if (right < left) {
            // 添加）
            dfs(n, left, right + 1, stringBuilder.append(')'));
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }
    }
}

第二中做法: 通过DFS 组合所有结果，过滤符合要求，组合的过程中（数量 > ）数量

import java.util.*;


public class Solution {
    /**
     * 设置结果
     */
    public static ArrayList<String> result = new ArrayList<>();
    // 左边括号
    public static int left = 0;

    // 右边括号
    public static int right = 0;
    /**
     *
     * @param n int整型
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        char[] target = new char[2 * n];
        boolean[] flag = new boolean[2 * n];
        for (int i = 0; i < 2 * n; i++) {
            if (i < n) {
                target[i] = '(';
                continue;
            }
            target[i] = ')';
        }
        dfs(target, flag, new StringBuilder());
        return result;
    }
    public void dfs(char[] target, boolean[] flag, StringBuilder stringBuilder) {
        // 结束循环条件
        if (right > left) {
            return;
        }
        // 结束条件
        if (stringBuilder.length() == target.length) {
            result.add(stringBuilder.toString());
            return;
        }
        for (int i = 0; i < target.length; i++) {
            // 结束标志 true || 去重
            if (flag[i] || i > 0 && target[i] == target[i - 1] && !flag[i - 1]) {
                continue;
            }
            // 前进
            flag[i] = true;
            if (target[i] == '(') {
                left++;
            } else {
                right++;
            }
            stringBuilder.append(target[i]);
            dfs(target, flag, stringBuilder);
            // 回退
            flag[i] = false;
            if (target[i] == '(') {
                left--;
            } else {
                right--;
            }
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }
    }
}

发表于 2022-04-09 23:47:23 回复(0)

Java

做一名拾荒者

    //记录结果
    ArrayList<String> res = new ArrayList<String>();

    public void recursion(int left, int right, String temp, int n){
        //递归终止
        if(left == n && right == n){
            res.add(temp);
            return;
        }
        //使用一次左括号
        if(left < n){
            recursion(left+1,right,temp+"(",n);
        }
        //使用右括号个数必须少于左括号
        if(right < n && left > right){
            recursion(left,right+1,temp+")",n);
        }
    }

    public ArrayList<String> generateParenthesis (int n) {
        recursion(0, 0, "", n);
        return res;
    }

递归 return 到底跑哪去了

发表于 2022-04-08 16:12:38 回复(0)

括号生成

输入

输出

输入

输出

暴力算法：DFS + 回溯

问题信息

热门推荐

通过挑战的用户

相关试题