text: // https://leetcode.com/problems/generate-parentheses/
  
  // Given n pairs of parentheses, write a function to generate all combinations of
  // well-formed parentheses.
  
  ////////////////////////////////////////////////////////////////////////////////
  
  // all combs -> dfs
  // count '(' and ')', generate ')' only when legal
  class Solution {
  public:
      vector<string> generateParenthesis(int n) {
          dfs(n, 0, 0);
          return ans;
      }
      
      void dfs(int n, int left, int right) {
          if (left == n and right == n) {
              ans.push_back(holder);
              return;
          }
          // generate children
          if (left < n) {
              holder.push_back('(');
              dfs(n, left + 1, right);
              holder.pop_back();
          }
          if (right < n && right < left) {
              holder.push_back(')');
              dfs(n, left, right + 1);
              holder.pop_back();
          }
      }
  private:
      vector<string> ans;
      string holder;
  };
  