题目描述

给定一个括号序列，请删除最少数量的括号，使得括号序列合法。返回所有删除方案。

注意： 输入的字符串中可能包含除了(和)以外的其他字符，直接保留即可。

样例1

Input: "()())()"
Output: ["()()()", "(())()"]

样例2

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

样例3

Input: ")("
Output: [""]

算法

(DFS+括号序列) $O(2^nn)$

这是一道有关括号序列的问题。那么如何判断一个括号序列是否合法呢？
判断方法：从前往后扫描字符串，维护一个计数器，遇到(就加一，遇到)就减一，如果过程中计数器的值都是非负数，且最终计数器的值是零，则括号序列是合法的。

左括号和右括号可以分开考虑，我们先来考虑删除哪些多余的右括号。
扫描字符串时，如果计数器的值小于0，说明前面的)太多，我们可以dfs暴力枚举删除前面哪些)，使得计数器的值大于等于0。
当处理完)后，我们只需将整个字符串逆序，同时把左右括号互换，就可以用相同的处理流程处理(了。

暴力dfs搜索空间比较高，我们要想办法进行剪枝。
剪枝方法：对于连续的)，不论删除哪一个，得到的方案都是相同的，所以我们对于所有连续的)，只枚举删除多少个。

剪枝后的算法在LeetCode上击败了100%的代码hh。

时间复杂度分析：我们先来考虑搜索空间有多大，最坏情况下，对于每个括号都有删或不删两种选择，所以共有 $2^n$ 种不同方案。对于每种方案，最后还需要 $O(n)$ 的计算量来记录答案，所以总时间复杂度是 $O(2^nn)$。

C++ 代码

class Solution {
public:
    vector<string> ans;
    unordered_set<string> S;

    vector<string> removeInvalidParentheses(string s) {
        dfs(s, 0, 0, false);
        return ans;
    }

    void dfs(string &s, int u, int ps, bool is_r)
    {
        if (u == s.size())
        {
            if (!is_r)
            {
                reverse(s.begin(), s.end());
                for (int i = 0; i < s.size(); i++)
                    if (s[i] == '(')
                        s[i] = ')';
                    else if (s[i] == ')')
                        s[i] = '(';
                dfs(s, 0, 0, true);
                reverse(s.begin(), s.end());
                for (int i = 0; i < s.size(); i++)
                    if (s[i] == '(')
                        s[i] = ')';
                    else if (s[i] == ')')
                        s[i] = '(';
            }
            else
            {
                string temp;
                for (int i = s.size() - 1; i >= 0; i--)
                    if (s[i] == '(') temp += ')';
                    else if (s[i] == ')') temp += '(';
                    else if (s[i] != '-') temp += s[i];
                if (!S.count(temp))
                {
                    ans.push_back(temp);
                    S.insert(temp);
                }
            }
            return;
        }
        if (s[u] != ')') dfs(s, u + 1, ps + (s[u] == '('), is_r);
        else
        {
            int i = u;
            while (i < s.size() && s[i] == ')') i++;
            ps -= i - u;
            if (ps >= 0) dfs(s, i, ps, is_r);
            else wipeoff(s, 0, i, -ps, is_r);
        }
    }

    void wipeoff(string &s, int start, int u, int ps, bool is_r)
    {
        if (start == u)
        {
            if (!ps) dfs(s, u, ps, is_r);
            return;
        }
        if (s[start] != ')') wipeoff(s, start + 1, u, ps, is_r);
        else
        {
            int k = start;
            while (k < u && s[k] == ')') k++;
            wipeoff(s, k, u, ps, is_r);
            for (int i = start, j = ps - 1; i < k && j >= 0; i++, j--)
            {
                s[i] = '-';
                wipeoff(s, k, u, j, is_r);
            }
            for (int i = start, j = ps - 1; i < k && j >= 0; i++, j--) s[i] = ')';
        }
    }
};