title: Balance ordering parenthesis via Dynamic programing
body: <p>Hi from the very famous book Code to Crack i come across a question :</p>
  
  <p>Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n-pairs of parentheses.</p>
  
  <p><em>Example</em>:</p>
  
  <pre><code>input: 3 (e.g., 3 pairs of parentheses)
  output: ()()(), ()(()), (())(), ((()))
  
  #include &lt;iostream&gt;
  #include &lt;string&gt;
  
  using namespace std;
  
  void _paren(int l,int r,string s,int count);
  void paren(int n)
  {
      string s="";
      _paren(n,n,s,n);
  }
  
  void _paren(int l,int r,string s,int count){
  
      if(l&lt;0 || r&lt;0)
          return;
      if(l==0 &amp;&amp; r==0)
          cout&lt;&lt;s&lt;&lt;endl;
      else{
          if(l&gt;0)
          {
              _paren(l-1,r,s+"(",count+1);
          }
          if(r&gt;l)
              _paren(l,r-1,s+")",count+1);                    
      }
  }
  int main(){
      int n;
      cin&gt;&gt;n;
      paren(n);
      return 0;
  }
  </code></pre>
  
  <p>This is a recursive approach I tried for it . I am pretty sure that we can solve this through dynamic programming as well , as we are already using a lot of value again and again , but I have no idea how to implement this through Dynamic programming I tried tabular bottom up approach but couldnt work out. Please help me out just the basic idea on how to work with this</p>