括号生成

class Solution:
    def generateParenthesis(self , n: int) -> List[str]:
        # write code here
        '''
        与全排列不同, 不需要首先生成再排序输出.
        '''
        def dfs(res, cur: str):
            if len(cur) == n * 2 and cur.count(')') == cur.count('('):
                res.append(cur)
            if cur.count(')') > cur.count('('): return # 递归过程中右括号数一定小于左括号数.
            if cur.count('(') > n: return

            dfs(res, cur + '(')
            dfs(res, cur + ')')

        res = []
        dfs(res, '')
        return res

import java.util.ArrayList;
public class Solution {
    static ArrayList<String> res = new ArrayList<>();
    public static ArrayList<String> generateParenthesis(int n) {
        f(0, 0, "", n);
        return res;
    }

    static void f(int left, int right, String temp, int n) {
        if (right == n) {
            res.add(new String(temp));
            return;
        }
                //左边的括号数量小于n
        if (left < n) {
            f(left + 1, right, temp + "(", n);
        }
                //右括号的数量在任意时刻都不能比左括号大。即不允许出现 “)” 找不到对应的“（”
        if (right < left) {
            f(left, right + 1, temp + ")", n);
        }
    }
}

//根据labuladong的回溯框架写了一个解法
class Solution {
private:
    int num_left;
    int num_right;
    vector<string> res;
public:
    vector<string> generateParenthesis(int n) {
        // write code here
        if(n == 0) return res;
        string tmp;
        num_left = n;   //'('的剩余数量
        num_right = n;  //'）'的剩余数量
        backtrack(tmp); //递归
        return res;
    }
    
    void backtrack(string tmp){
        if(num_left == 0 && num_right == 0){  //结束条件
            res.push_back(tmp);
            return;
        }
        
        for(int i = 0;i < 2;i++){
            if(!isInsert(tmp,i)){    //判断当前位置能否插入'('或')'
                continue;
            }
            //选择
            if(i == 0){              
                tmp.push_back('(');
                num_left--;
            }
            else{
                tmp.push_back(')');
                num_right--;
            }
            
            backtrack(tmp);
            
            //撤销选择
            if(tmp[tmp.length() - 1] == '('){
                num_left++;
            }
            else{
                num_right++;
            }
            tmp = tmp.substr(0,tmp.length()-1);
        }
    }
    
    bool isInsert(string tmp,int i){
        if(num_right == num_left && i == 1){    //当'('和')'剩余数量相同时，不允许选择')'
            return false;
        }
        if(tmp.length() == 0 && i == 1){      //第一次选择时，不允许选择')'
            return false;
        }
        //当'('或')'剩余数量为0时，不允许选择
        if((i == 0 && num_left == 0) || (i == 1 && num_right == 0)){  
            return false;
        }
        return true;
    }
    
};

class Solution {
public:
  /**
   * 
   * @param n int整型 
   * @return string字符串vector
   */
  vector<string> generateParenthesis(int n) {
    vector<string> ans;
    string candidates;
    function<void(int, int)> backtracking_algorithm = 
        [&](int l, int r) -> void {
      
      if (candidates.length() == n << 1)
        return ans.push_back(candidates);
      
      if (l < n) {
        candidates.push_back('(');
        backtracking_algorithm(l + 1, r);
        candidates.pop_back();
      }
      
      if (r < l) {
        candidates.push_back(')');
        backtracking_algorithm(l, r + 1);
        candidates.pop_back();
      }
    };
    
    backtracking_algorithm(0, 0);
    return ans;
  }
};

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    ArrayList<String> res = new ArrayList<>();
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        if(n < 1) return res;
        dfs(new StringBuilder(), n, n);
        return res;
    }
    private void dfs(StringBuilder sb,int left, int right) {
        //左右括号都用完了，返回
        if(left == 0 && right == 0) {
            res.add(sb.toString());
            return;
        }
        //先让左括号生成，然后再根据左括号的情况生成右括号
        if(left > 0) {
            sb.append("(");
            dfs(sb, left-1, right);
            sb.delete(sb.length()-1, sb.length());
        }
        if(right > 0 && right > left) {
            sb.append(")");
            dfs(sb,left,right-1);
            sb.delete(sb.length()-1, sb.length());
        }
        
    }
}

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        if(n==0) return ans;
        string tmp = "";
        dfs(2*n,n,ans,tmp,0,0);
        return ans;
    }
    void dfs(int n,int k,vector<string>& ans,string& tmp,int left,int right){
        if(n==0&&isValid(tmp)){
            ans.push_back(tmp);
            return;
        }
        if(left<k){//添加左括号
            tmp.push_back('(');
            dfs(n-1,k,ans,tmp,left+1,right);
            tmp.pop_back();
        }
        if(right<k){//添加右括号
            tmp.push_back(')');
            dfs(n-1,k,ans,tmp,left,right+1);
            tmp.pop_back();
        }
    }
    bool isValid(string s){
        stack<char> stk;
        for(auto c:s){
            if(c=='(') stk.push(c);
            if(c==')'){
                if(stk.empty()) return false;
                char top = stk.top();
                if(top=='(') stk.pop();
                else return false;
            }
        }
        if(!stk.empty()) return false;
        return true;
    }
};

class Solution {
public:
    void generateParenthesisAux(int n, int x, int y, string s, vector<string> &ans){
        if(y == n) ans.push_back(s);
        if(x < n) generateParenthesisAux(n, x+1, y, s+"(", ans);
        if(x > y) generateParenthesisAux(n, x, y+1, s+")", ans);
    }
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        generateParenthesisAux(n, 0, 0, "", ans);
        return ans;
    }
};

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

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

    // 关键：right≤left≤n，当right=left=n时即为一个解
    private void gp(String s, int left, int right, int n) {
        if (right == n) {
            r.add(s);
        }
        if (left < n) {
            gp(s + "(", left + 1, right, n);
        }
        if (right < left) {
            gp(s + ")", left, right + 1, n);
        }
    }

vector<string> generateParenthesis(int n) {
        vector<string> res;
        if(n==0) return res;
        string path;
        dfs(0,0,n,path,res);
        return res;
    }
    
    void dfs(int useLeft,int useRight,int n,string &path,vector<string> &res){
        int remLeft=n-useLeft;
        int remRight=n-useRight;
        if(remLeft==0&&remRight==0){
            res.push_back(path);
            return;
        }
        int minLeft=0;
        if(useLeft==useRight) minLeft=1;
        for(int i=remLeft;i>=minLeft;--i){
                string tmp;
                for(int j=1;j<=i;++j)
                    tmp.push_back('(');
                tmp.push_back(')');
                path+=tmp;
                dfs(useLeft+i,useRight+1,n,path,res);
                for(int j=0;j<i+1;++j)
                    path.pop_back();
            }
    }

#include <stdio.h>

/*
Write a function Brackets(int n) that prints all combinations of well-
formed brackets. For Brackets(3) the output would be ((())) (()()) (())
() ()(()) ()()()

You can approach this the same way you'd do it by hand.  Build up the
string of brackets left to right.  For each position, you have a
decision of either ( or ) bracket except for two constraints:
(1) if you've already decided to use n left brackets, then you can't
use a another left bracket and
(2) if you've already used as many right as left brackets, then you
can't use another right one.

This suggests the following alorithm. Showing what happens on the
stack is a silly activity.
*/

// Buffer for strings of ().
char buf[1000];

// Continue the printing of bracket strings.
//   need is the number of ('s still needed in our string.
//   open is tne number of ('s already used _without_ a matching ).
//   tail is the buffer location to place the next ) or (.
void cont(int need, int open, int tail)
{
    // If nothing needed or open, we're done.  Print.
    if (need == 0 && open == 0) {
        printf("%s\n", buf);
        return;
    }

    // If still a need for (, add a ( and continue.
    if (need > 0) {
        buf[tail] = '(';
        cont(need - 1, open + 1, tail + 1);
    }

    // If still an open (, add a ) and continue.
    if (open > 0) {
        buf[tail] = ')';
        cont(need, open - 1, tail + 1);
    }
}

void Brackets(int n)
{
    cont(n, 0, 0);
}

int main(void)
{
    Brackets(4);
    return 0;
}

import java.util.ArrayList;
public class Solution {
    ArrayList<String> r = new ArrayList<String>();
    public ArrayList<String> generateParenthesis(int n) {
        //保证左边‘（’的数量始终大于等于右边的‘）’数量，可以考虑回溯法
        ArrayList<String> s = new ArrayList<String>();
        gp("",0,0,n);
        return r;
    }
    private void gp(String s,int left,int right,int n){
        if(right == n){
            r.add(s);
        }
        if(left < n){
            gp(s+"(",left+1,right,n);
        }
        // 递归过程中 左括号x的个数必须大于等于右括号个数
        if(left > right){
            gp(s+")",left,right+1,n);
        }
    }
}

vector<string> generateParenthesis(int n){
    vector<set<string>> res;
    res.resize(n+1);
    set<string> st;
    if(n<=0) return vector<string>();
    res[0] = {""};
    for(int m=1; m<=n;++m){
        //  { f(1)f(n-1) + f(2)f(n-2) + ... + f(n-1)f(n) } for(int i=1; i<m;++i){
            for(string l: res[i])
                for(string r: res[m-i])
                    res[m].insert(l+r);
        }
        //  {"(" + f(n-1)) +")" } 
        for(string s: res[m-1]){
            res[m].insert(string("(")+s+string(")"));
        }
    }
    vector<string> vec;
    for(string s: res[n]){
        vec.push_back(s);
    }
    return vec;
}

 left代表左括号剩余个数，right同理
1.每部递归注意递归体即有几种可选的操作  +'('  or + ')'
2.考虑操作的限制条件，加右括号时满足左括号的剩余个数<右括号
3.递归退出条件，左右括号个数都用光即可

//字符串+操作相当于push，如果字符串个数少从0到1递归
void generateParenthesisDfs(vector<string> &res, int left, int right, string cur){
    //3.跳出条件
    if(left == 0 && right == 0){
        res.push_back(cur);
    }
    
    //1.choice
    if(left > 0) generateParenthesisDfs(res, left - 1, right, cur + '(');
    
    //2.constrain
    if(right > 0 && right > left) generateParenthesisDfs(res, left, right - 1, cur + ')');
    
}

vector<string> generateParenthesis(int n) {
    vector<string> res;
    if(n < 1) return res;
    int left = n, right = n;
    generateParenthesisDfs(res, left, right, "");
    return res;
}

	

class Solution:
    def generateParenthesis(self , n: int) -> List[str]:
        if n==1:return ["()"]
        lst = []
        for s in self.generateParenthesis(n-1):
            for i in range(len(s)):
                temp = s[:i] + "()" + s[i:]
                lst.append(temp)
        return list(set(lst))

/*输出得按顺序这个就比较无奈了
采用递归
每次左括号比右括号多时可以加左括号或者右括号
如果左括号等于右括号则只能加左括号
左括号够了那就只加右括号
右括号够了那就只加左括号
*/
class Solution {
public:
    void generate(vector<string>&v,int x,int y,string s){
        if(x==0&&y==0){
            v.push_back(s);
            return;
        }
        if(x==0&&y>0){
            generate(v,x,y-1,s+")");
            return;
        }
        if(y==0&&x>0){
            generate(v,x-1,y,s+"(");
            return;
        }
        if(x<y){
            generate(v,x-1,y,s+"(");
            generate(v,x,y-1,s+")");
            return;
        }
        if(x>=y){
            generate(v,x-1,y,s+"(");
            return;
        }
    }
    vector<string> generateParenthesis(int n) {
            vector<string>ret;
            string s="";
            generate(ret,n,n,s);
            return ret;
    }
};

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    vector<string> generateParenthesis(int n) {
        // 时间复杂度O(2^N)，空间复杂度O(N)
        vector<string> res;
        string path;
        recursion(0, 0, n, path, res);
        return res;
    }
    void recursion(int left, int right, int n, string &path, vector<string> &res) {
        if (left == n && right == n) {
            res.push_back(path);
            return;
        }
        if (left < n) {
            path.push_back('(');
            recursion(left + 1, right, n, path, res);
            path.pop_back();
        }
        if (right < n && right < left) {
            path.push_back(')');
            recursion(left, right + 1, n, path, res);
            path.pop_back();
        }
    }
};

class Solution {
public:
    vector<string> generateParenthesis(int n) {
          vector<string> ans;
          dfs(0,0,2*n,"",ans);
          return ans;
    }
    void  dfs(int l,int r,int n,string tmp,vector<string> &ans){
          if(l+r==n) {ans.push_back(tmp);return;}
          if(r<n/2) dfs(l,r+1,n,tmp+"(",ans);
          if(l<r) dfs(l+1,r,n,tmp+")",ans);
    }
};