leetcode/generateParentheses.cpp at master · outman119/leetcode · 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
43
44
45
class Solution {
public:
    vector<string> generateParenthesis(int n) {
       vector<string>ret;
        if (n <= 0)
        {
            return ret;
        }
        string s;
        s.push_back('(');
        int count = 1;
        int index = 1;
        getPa(n*2, index, count, s, ret);
        return ret;
    }
private:
    void getPa(int n, int index, int count, string &s, vector<string>&ret)
    {
        if (s.length() == n && count == 0)
        {
            ret.push_back(s);
            return;
        }
        if (count < 0)
        {
            return;
        }
        for (int i = index; i < n; i++)
        {
            //push (
            s.push_back('(');
            count++;
            getPa(n, i + 1, count, s, ret);
            s.pop_back();
            count--;
            //push )
            s.push_back(')');
            count--;
            getPa(n, i + 1, count, s, ret);
            s.pop_back();
            count++;
        }
        return;
    }
};