Leetcode: Generate parentheses

 1 class Solution {
 2 public:
 3     void helperDFS(int n, int x, int y, string now, vector<string> &ans) {
 4         if (y == n) {
 5             ans.push_back(now);
 6             return;
 7         }
 8         if (x < n) {
 9             helperDFS(n, x + 1, y, now + "(", ans);
10         }
11         if (x > y) {
12             helperDFS(n, x, y + 1, now + ")", ans);
13         }
14         
15     }
16     vector<string> generateParenthesis(int n) {
17         vector<string> ans;
18         helperDFS(n, 0, 0, "", ans);
19         return ans;
20     }
21 };

 1 struct node{
 2     int x, y;
 3     string now;
 4 };
 5 class Solution {
 6 public:
 7     void helperBFS(int n, vector<string> &ans) {
 8         if (0 == n) {
 9             ans.push_back("");
10             return;
11         }
12         node tmp;
13         tmp.x = tmp.y = 0;
14         tmp.now = "";
15         queue<node> q;
16         for (q.push(tmp); !q.empty(); q.pop()) {
17             tmp = q.front();
18             node other;
19             if (tmp.x < n) {
20                 other.x = tmp.x + 1;
21                 other.y = tmp.y;
22                 other.now = tmp.now + "(";
23                 q.push(other);
24             }
25             if (tmp.x > tmp.y) {
26                 other.x = tmp.x;
27                 other.y = tmp.y + 1;
28                 other.now = tmp.now + ")";
29                 if (other.y == n) {
30                     ans.push_back(other.now);
31                 } else {
32                     q.push(other);
33                 }
34             }
35         }
36         
37     }
38     vector<string> generateParenthesis(int n) {
39         vector<string> ans;
40         helperBFS(n, ans);
41         return ans;
42     }
43 };