C++ solution


  • 0
    N

    Here is a C++ solution,

    class Solution {
    public:
        bool isValid(const string& parens) {
            int balanced = 0;
            for (auto it = parens.begin(); *it != '\0'; ++it) {
                if (*it == '(') ++balanced;
                else --balanced;
                if (balanced < 0) return false;
            }
            return 0 == balanced;
        }
        vector<string> generateParenthesis(int n) {
            vector<string> res;
            if (n == 0) return res;
            string start(2*n+1, 0);
            std::fill_n(start.begin(), n, '(');
            std::fill_n(start.begin() + n, n, ')');
            res.push_back(start); // start with (((...)))
            // permute except the first ( and last )
            auto s = start.begin() + 1;
            auto e = s + 2*n - 2;
            while (next_permutation(s, e)) {
                if (isValid(start))
                    res.emplace_back(start);
            }
            return res;
        }
    };
    

    Note that there is scope for optimizing next_permutation to avoid out of balance permutations.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.