22 - Generate Parentheses

 JAVA

• class Solution {
      private List<String> ans = new ArrayList<>();
      private int n;
  
      public List<String> generateParenthesis(int n) {
          this.n = n;
          dfs(0, 0, "");
          return ans;
      }
  
      private void dfs(int l, int r, String t) {
          if (l > n || r > n || l < r) {
              return;
          }
          if (l == n && r == n) {
              ans.add(t);
              return;
          }
          dfs(l + 1, r, t + "(");
          dfs(l, r + 1, t + ")");
      }
  }

C++

• class Solution {
  public:
      vector<string> generateParenthesis(int n) {
          vector<string> ans;
          function<void(int, int, string)> dfs = [&](int l, int r, string t) {
              if (l > n || r > n || l < r) return;
              if (l == n && r == n) {
                  ans.push_back(t);
                  return;
              }
              dfs(l + 1, r, t + "(");
              dfs(l, r + 1, t + ")");
          };
          dfs(0, 0, "");
          return ans;
      }
  };