301. 删除无效的括号

https://leetcode-cn.com/problems/remove-invalid-parentheses/

一、回溯+少量剪枝

首先计算最少删除左右括号数量lremove和rremove，即剪枝减少递归层数：

对字符串每个位置i（i从0~n-1）尝试删除，在递归中带入lremove和rremove，降为0就是递归出口。

class Solution:
    def removeInvalidParentheses(self, s: str):
        res = set()	 #去重
        # 计算最少删除左右括号数量
        lremove, rremove = 0, 0
        for c in s:
            if c == '(':
                lremove += 1
            elif c == ')':
                #左括号数为0时，右括号数加一；否则左括号数减一（抵消）
                if lremove == 0:
                    rremove += 1
                else:
                    lremove -= 1

        # 辅助函数：校验括号是否合法
        def isValid(str):
            cnt = 0
            for c in str:
                if c == '(':
                    cnt += 1
                elif c == ')':
                    cnt -= 1
                    if cnt < 0:
                        return False
            return cnt == 0

        #回溯函数
        #lremove，rremove分别为要删除的左右括号
        def bt(s, start, lremove, rremove):
            if lremove == 0 and rremove == 0:	#递归出口
                if isValid(s):  #括号合法才记录
                    res.add(s)
                return
            for i in range(start, len(s)):        
                 # 如果剩余的字符无法满足去掉的数量要求，直接返回
                if lremove + rremove > len(s) - i:
                    return
  
                # 尝试去掉一个左括号
                if lremove > 0 and s[i] == '(':
                    bt(s[:i] + s[i + 1:], i, lremove - 1, rremove)
                # 尝试去掉一个右括号
                if rremove > 0 and s[i] == ')':
                    bt(s[:i] + s[i + 1:], i, lremove, rremove - 1)

		# 进行回溯
        bt(s, 0, lremove, rremove)
        return list(res)

再优化

再剪枝，去除连续相同的括号的情况，

比如当前遇到的字符串为 "(((())"，去掉前四个左括号中的任意一个，生成的字符串是一样的，均为"((())"

还有就是递归过程中，当右括号数量超过左括号时可以直接return(待实现)