搜索

搜索

dfs

22.括号生成

/**
 * 2024-10-12
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
    const ans = [];
    const all = n * 2;
    let path = new Array(all);
    function dfs(left, cnt) {
        if (cnt === all) {
            ans.push(path.join(''));
            return;
        }
        if (left < n) {
            path[cnt] = '(';
            dfs(left + 1, cnt + 1);
        }
        if (cnt - left < left) {
            path[cnt] = ')';
            dfs(left, cnt + 1);
        }
    }
    dfs(0, 0);
    return ans;
};

这道题需要注意，终止条件是当当前的括号数量等于 2n 时，将当前的路径加入到结果中。 其中两个条件是，左括号的数量小于 n 时，可以添加左括号，右括号的数量小于左括号的数量时，可以添加右括号。

bfs