[数据结构与算法]LeetCode《程序员面试金典》面试题 08.09. 括号

题目

解题

从头开始构造字符串，从而避免出现重复字符串。在这个解法中只要字符串仍然有效，逐一加入左括号和右括号。每次递归调用，都会有个索引值对应字符串的某个字符。我们需要选择左括号或右括号，那么，何时可以用左括号，何时可以用右括号呢?

(1) 左括号：只要左括号还没有用完，就可以插入左括号。
(2) 右括号：只要不造成语法错误，就可以插入右括号。何时会出现语法错误？如果右括号
比左括号还多，就会出现语法错误。

// javascript
var generateParenthesis = function(n) {
    let str = new Array(n * 2), list = new Array();
    addParen(list, str, 0, n, n);
    return list;
};

var addParen = function(list, str, index, leftRem, rightRem) {
    if (leftRem < 0 || leftRem > rightRem) return; // 无效状态
    if (leftRem === 0 && rightRem === 0) {         // 没有左右括号了  
        list.push(str.join(""));
    } else {
        // 插入左括号并递归（不用修改str的index+1往后的值，因为递归会改到）
        str[index] = "(";
        addParen(list, str, index + 1, leftRem - 1, rightRem);
        // 插入右括号并递归（不用修改str的index+1往后的值，因为递归会改到）
        str[index] = ")";
        addParen(list, str, index + 1, leftRem, rightRem - 1);
    }
};