fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void generateSequence(int numOpened, int numClosed, string seq, int n, vector<string>& combinations) {
  5.     if(seq.size() == 2 * n) {
  6.         // base case: if the size of the sequence is 2*n, so we put n opening '('
  7.         // and n closing ')', so a valid was produced
  8.         combinations.push_back(seq);
  9.         return;
  10.     }
  11.     if(numOpened < n) {
  12.         // put an opening '(' if the number of opened '(' < n
  13.         generateSequence(numOpened + 1, numClosed, seq + '(', n, combinations);
  14.     }
  15.     if(numClosed < numOpened) {
  16.         // put a closing ')' only if there is unmathced opened '(', i.e.,
  17.         // the number of closed ')' is strictly less than the number of opened '('
  18.         generateSequence(numOpened, numClosed + 1, seq + ')', n, combinations);
  19.     }
  20. }
  21.  
  22. vector<string> generateParentheses(int n) {
  23.     // wrapper function
  24.     vector<string> combinations; // an array of all valid sequences produced
  25.     // start the sequence with 0 opening '(' and 0 closed ')' with an empty sequence "" 
  26.     generateSequence(0, 0, "", n, combinations);
  27.     return combinations; // return the array after filling it
  28. }
  29.  
  30. int main() {
  31.  
  32.     int n = 4;
  33.  
  34.     vector<string> combinations = generateParentheses(n);
  35.     // output the valid sequences produced
  36.     cout << "For n = " << n << ", the number of valid combinations producded = " << combinations.size() << '\n';
  37.     for(auto&combination:combinations) cout << combination << '\n';
  38.  
  39.     return 0;
  40. }
  41.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
Standard input is empty
stdout 
For n = 4, the number of valid combinations producded = 14
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
https://ideone.com/VHDFkg
language:
C++14 (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!