leetcode

0 class Solution {

1 unordered_set<string> st;

2 int maxi = 0;

3

4 void rec(const string &s, int idx, const string &crnt, int open, int close) {

5 if (idx == size(s)) {

6 if (open != 0) return;

7

8 if (size(crnt) > maxi) {

9 maxi = size(crnt);

10 st.clear();

11 }

12

13 if (size(crnt) == maxi && !st.count(crnt)) {

14 st.insert(crnt);

15 }

16

17 return;

18 }

19

20 if (s[idx] == '(') {

21 if (open + 1 <= close) rec(s, idx + 1, crnt + '(', open + 1, close);

22 rec(s, idx + 1, crnt, open, close);

23 } else if (s[idx] == ')') {

24 if (open > 0) rec(s, idx + 1, crnt + ')', open - 1, close - 1);

25 rec(s, idx + 1, crnt, open, close);

26 } else

27 rec(s, idx + 1, crnt + s[idx], open, close);

28 }

29

30 public:

31 vector<string> removeInvalidParentheses(const string &s) {

32 rec(s, 0, "", 0, count(begin(s), end(s), ')'));

33 return vector(begin(st), end(st));

34 }

35 };