括号生成

import java.util.*;

public class Solution {
    public ArrayList<String> generateParenthesis (int n) {
        ArrayList<String> list = new ArrayList<>();
        generate(n, 0, 0, "", list);   // 调用
        return list;
    }

    // ()生成
    public void generate(int n, int left, int right, String s, List<String>list) {
        if (left < right || left > n || right > n) return; // 括号不匹配情况

        if (left == n && right == n) { // n个()，加入list
            list.add(s);
            return;
        }

        generate(n, left + 1, right, s + '(', list);  // 1个（
        generate(n, left, right + 1, s + ')', list);  // 1个 ）
    }
}

参考官方题解，整合了一下判断条件

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);
    }
}

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);
        }
    }
}

一种迭代状态的写法：

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;
    }
}

 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);
        }
    }

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);
        }
    }

}

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);
        }          
    }
}

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;
    }
}

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);
        }
    }
}

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);
           }
        }
    }

    // 没有想到这就写出来了，虽然和答案不太一样，答案是有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);
    }

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++;
            
        }
        
    }
}

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;
    }
}

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);
        }
    }
}

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);
    }
}

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);
        }
    }
}