<blockquote id="shwb3"><ruby id="shwb3"></ruby></blockquote>
  • <small id="shwb3"><strong id="shwb3"></strong></small>

      1. <big id="shwb3"></big>
        1. 首页 > 其他 > 详细

          22. Generate Parentheses dfs填表

          时间:2019-03-10 13:15:45      阅读:36      评论:0      收藏:0      [点我收藏+]

          标签:进行   ios   int   title   dfs   names   思路   pac   ace   

          22. Generate Parentheses
          Medium

          Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

          For example, given n = 3, a solution set is:

          [
            "((()))",
            "(()())",
            "(())()",
            "()(())",
            "()()()"
          ]
          思路:
            如果n=1,那么最终结果都是2个符号,如果n=3,最终结果都是6个符号,所以只需要开一个2*n+1的字符数组
          枚举左右括号即可,第2*n个字符用于保存‘\0‘(字符串结束标记),这样的时间复杂度是2^n次方。由于这样枚举
          出来的结果中?#34892;?#22810;不?#25103;ǎ?#25152;以可以进行剪枝处理。
              1)第一个位置一定填充左括号
              2)如果当前的右括号个数大于左括号一定是错误的
              3)如果左括号个数大于一半,则一定不?#25103;?/span>
          #include<iostream>
          #include<bits/stdc++.h>
          using namespace std;
          
          void solve(vector<string>&ans,int n,int i,int left,int right,char ch[])
          {
              if(left>n)
                  return;
              if(i == 2*n)
              {
                  ans.push_back(ch);
                  return;
              }
              ch[i]=(;
              solve(ans,n,i+1,left+1,right,ch);
              if(right<left)
              {
                  ch[i]=);
                  solve(ans,n,i+1,left,right+1,ch);
              }
          }
          
          
          vector<string> generateParenthesis(int n)
          {
              vector<string>ans;
              if(n==0)
                  return ans;
              char ch[2*n+1];
              ch[0]=(;
              ch[2*n]=\0;
              solve(ans,n,1,1,0,ch);
              return ans;
          }
          
          int main()
          {
              vector<string>ans;
              ans=generateParenthesis(1);
              for(int i=0;i<ans.size();i++){
                  cout<<ans[i]<<endl;
              }
              return 0;
          }
          
          

           



          22. Generate Parentheses dfs填表

          标签:进行   ios   int   title   dfs   names   思路   pac   ace   

          原文:https://www.cnblogs.com/zhanghaijie/p/10504913.html

          (0)
          (0)
             
          举报
          评论 一句话评论(0
          0条  
          登录后才能评论!
          ? 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
          打开技术之扣,分享程序人生!
                       

          ?#24443;?#32593;安备 37021202000002号

          t6娱乐平台官方
          <blockquote id="shwb3"><ruby id="shwb3"></ruby></blockquote>
        2. <small id="shwb3"><strong id="shwb3"></strong></small>

            1. <big id="shwb3"></big>
              1. <blockquote id="shwb3"><ruby id="shwb3"></ruby></blockquote>
              2. <small id="shwb3"><strong id="shwb3"></strong></small>

                  1. <big id="shwb3"></big>