A special && easy Solution


  • 0
    H
    class Solution {
    public:
        /**
         * a valid combination of parentheses fit two features:
         *      1. count(`(`) == count(`)`);
         *      2. with a well-formed combination `s`. s[0:i] fit that count(`(`) >= count(`)`)  
         * we can use a binary number to represent a  combination of parentheses: 
         * 1 => `}` and 0 => `{` . For example: "((()))" =>  000111.
         * With given `n`, there is 2^n possible combinations to enumerate. 
         */ 
        vector<string> generateParenthesis(int n) {
            int num = (1<<(2 * n));
            vector<string> res;
            for(int i = 0; i < num; ++i) {
                auto parentheses = TryParse(i, 2*n);
                if(!parentheses.empty()) {
                    res.push_back(parentheses);
                }
            }
            return res;
        }
        
        string TryParse(int target, int parentheses_len) {
            string parentheses;
            int left_bracket_count = 0 , right_bracket_count = 0; 
            for(int i = parentheses_len - 1;  i >= 0; i --) {
                bool  is_right_bracket = (target &(1<<i));
                if(is_right_bracket) {
                    parentheses.append(")");
                    right_bracket_count ++;
                }
                else {
                    parentheses.append("(");
                    left_bracket_count ++;
                }
                if (left_bracket_count < right_bracket_count || left_bracket_count > parentheses_len/2) {
                    return "";
                }
            }
            return parentheses;
        }
        
    };
    

Log in to reply
 

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