DataStructures-Algorithms/Leetcode Top Interview Questions/solutions/Generate Parentheses.cpp at master · arjunkumar09/DataStructures-Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
Generate Parentheses
====================

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

Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:
Input: n = 1
Output: ["()"]

Constraints:
1 <= n <= 8
*/

class Solution
{
  void backtrack(vector<string> &ans, int n, int open, int close, string out = "")
  {
    if (out.length() == n * 2)
    {
      ans.push_back(out);
      return;
    }

    if (open < n)
      backtrack(ans, n, open + 1, close, out + "(");
    if (close < open)
      backtrack(ans, n, open, close + 1, out + ")");
  }

public:
  vector<string> generateParenthesis(int n)
  {
    vector<string> ans;
    backtrack(ans, n, 0, 0);
    return ans;
  }
};