括号生成

[pwstrick]

22. 括号生成

/**
 * @param {number} n
 * @return {string[]}
 */
let results;
var generateParenthesis = function(n) {
    results = [];
    let route = [];
    n *= 2;
    backtrack(route, 0, n);
    return results;
};

function backtrack(route, pos, n) {
    if(pos == n) {
        valid(route) && results.push(route.join(""));
        return;
    }
    route[pos] = "(";               //选择
    backtrack(route, pos+1, n);
    route[pos] = ")";               //撤销
    backtrack(route, pos+1, n);
}
//验证当前括号配对是否合法
function valid(route) {
    let balance = 0;
    for(let p of route) {
        if(p == "(")
            balance++;
        else if(p == ")")
            balance--;
        if(balance < 0)
            return false;
    }
    return balance == 0;
}