301. 删除无效的括号

func check (s string) (int, int) {
    left := 0
    right := 0
    for _,bracket := range s {
        bracketStr := string(bracket)
        if bracketStr == "(" {
            left++
        } else if bracketStr == ")" {
            if left > 0 {
                left--
            } else {
                right++
            }
        }
    }
    return left, right
}

func removeInvalidParenthesesHelper(s string, i int, pair int, left int, right int, solution string, m map[string]int) {
    if i >= len(s) {
        // 完全匹配
        if pair == 0 && left == 0 && right == 0 {
            m[solution] = 1
        }
        return
    }
    char := string(s[i])
    if char == "(" {
        if left > 0 {
            // 计算一遍将其删去的情况
            removeInvalidParenthesesHelper(s, i + 1, pair, left - 1, right, solution, m)
        }
        // 计算一遍不将其删去的情况
        removeInvalidParenthesesHelper(s, i + 1, pair + 1, left, right, solution + char, m)
    } else if char == ")" {
        if right > 0 {
            removeInvalidParenthesesHelper(s, i + 1, pair, left, right - 1, solution, m)
        }
        // 防止出现无法配对的情况
        if pair > 0 {
            removeInvalidParenthesesHelper(s, i + 1, pair - 1, left, right, solution + char, m)
        }
    } else {
        removeInvalidParenthesesHelper(s, i + 1, pair, left, right, solution + char, m)
    }
}

func removeInvalidParentheses(s string) []string {
    cLeft, cRight := check(s)
    m := make(map[string]int)
    removeInvalidParenthesesHelper(s, 0, 0, cLeft, cRight, "", m)
    keys := []string{}
    for key := range m {
        keys = append(keys, key)
    }
    return keys
}