Leetcode Remove Invalid Parentheses problem solution

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        def check(s):
            count = 0 
            for i in s:
                if i =='(':
                    count += 1
                elif i == ')':
                    count -= 1 
                    if count < 0 :
                        return False
            return count == 0 
        
        dict1 ={s}
        while True:
            temp = []
            for i in dict1:
                if check(i):
                    temp.append(i)
            if temp:
                return temp 
            
            new_set = set()
            for i in dict1:
                for j in range(len(i)):
                    new_set.add(i[:j]+i[j+1:])
            dict1 = new_set

class Solution {
    private Set<String> candidates;
    private int min;
    private String s;
    
    private boolean isBraket(char c) {
        return c == '(' || c == ')';
    }
    
    public void recurse(StringBuilder buf, int idx, int left, int right, int removed) {
        if (right > left || removed > min) {
            return;
        }
        
        if (idx == s.length()) {
            if (left != right) {
                return;
            }
            
            if (removed < min) {
                candidates.clear();
                min = removed;
            }
            
            candidates.add(buf.toString());
            return;
        }
        
        char c = s.charAt(idx);
        if (isBraket(c)) {
            recurse(buf, idx+1, left, right, removed+1);
            buf.append(c);
            boolean isLeft = (c == '(');
            recurse(buf
                    , idx+1
                    , isLeft ? left + 1 : left
                    , isLeft ? right : right + 1
                    , removed);
        } else {
            buf.append(c);
            recurse(buf, idx+1, left, right, removed);
        }
        buf.deleteCharAt(buf.length()-1);
    }
    
    public List<String> removeInvalidParentheses(String s) {
        this.s = s;
        this.min = Integer.MAX_VALUE;
        this.candidates = new HashSet<>();
        
        recurse(new StringBuilder(), 0, 0, 0, 0);
        return new ArrayList<>(this.candidates);
    }
}

int getmin(string str)
{
	stack<char> st;
	st.push('a');
	for (int i=0;i<str.size();i++)
	{
		char ch = str[i];
		if (ch == '(')
		{
			st.push(ch);
		} else if ( ch == ')')
		{
			if ( st.top() == '(')
			{
				st.pop();
			} else {
				st.push(')');
			}
		}
	}
	return st.size()-1;
}

void traverse(char* s, int len, int start, int left, int right, int pair, char* stack, int top, char*** arr, int *returnSize)
{
    if(start == len)
    {
        if(!left && !right && !pair)
        {
            int size = top+1;
            char *t = (char*)malloc(sizeof(char)*(size+1));
            for(int i = 0; i < size; i++)
                t[i] = stack[i];
            t[size] = '';
            int i = 0;
            while(i < *returnSize)
            {
                if(!strcmp(t, (*arr)[i]))
                    break;
                i++;
            }
            if(i == *returnSize)
            {
                *returnSize += 1;
                *arr = (char**)realloc(*arr, sizeof(char*)*(*returnSize));
                (*arr)[*returnSize-1] = t;
            }
        }
        return ;
    }
    char c = s[start];
    if(c == '(')
    {
        if(left)
            traverse(s, len, start+1, left-1, right, pair, stack, top, arr, returnSize);
        stack[top+1] = c;
        traverse(s, len, start+1, left, right, pair+1, stack, top+1, arr, returnSize);
    }
    else if(c == ')')
    {
        if(right) =
            traverse(s, len, start+1, left, right-1, pair, stack, top, arr, returnSize);
        if(pair)
        {
            stack[top+1] = c;
            traverse(s, len, start+1, left, right, pair-1, stack, top+1, arr, returnSize);
        }
    }
    else
    {
        stack[top+1] = c;
        traverse(s, len, start+1, left, right, pair, stack, top+1, arr, returnSize);
    }
}

char** removeInvalidParentheses(char* s, int* returnSize)
{
    char** arr = (char**)malloc(sizeof(char*));
    *returnSize = 0;
    int left=0, right=0;
    for(int i = 0; s[i]; i++) 
    {
        if(s[i] == '(') left++;
        else if(s[i] == ')')
        {
            if(left) left--;
            else right++;
        }
    }
    int len = strlen(s);
    char *stack = (char*)malloc(sizeof(char)*len);
    int top = -1;
    traverse(s, len, 0, left, right, 0, stack, top, &arr, returnSize);
    return arr;
}