leetcode22.括号生成

1.题目要求:

2.题目代码:

class Solution {
public:
    vector<string> result;
    string str;
    //判断字符串是否为有效括号
    bool isValid(string s) {
        stack<char> v;
        for(int i = 0;i < s.size();i++){
            if(s.at(i) == '('){
                v.push(')');
            }else{
                    if(v.size() == 0){
                        return false;
                    }
                    if(s.at(i) == v.top()){
                        v.pop();
                    }else{
                        return false;
                    }
            }
        }
        if(v.size() != 0){
            return false;
        }else{
            return true;
        }
    }
    //开始回溯
    void backtricking(string path,vector<bool>& used){
        //如果字符串的长度等于path的长度，则进行判断是否为有效括号，如果是，则放入答案数组
        if(str.size() == path.size()){
            if(isValid(str) == true){
                result.push_back(str);
            }
        }
        for(int i = 0;i < path.size();i++){
            //判断是否有重复括号
            if(i > 0&&path[i] == path[i - 1]&&used[i - 1] ==false){
                continue;
            }
            if(used[i] == false){
                str += path[i];
                used[i] = true;
                backtricking(path,used);
                //回溯的表达式
                str.pop_back();
                used[i] = false;
            }else{
                continue;
            }
        }
    }
    vector<string> generateParenthesis(int n) {
        string path;
        int i = 0;
        while(i < n){
            path += '(';
            i++;
        }
        i = 0;
        while(i < n){
            path += ')';
            i++;
        }
        vector<bool> used;
        used.resize(path.size(),false);
        backtricking(path,used);
        return result;
    }
};