Generate Parentheses

22. Generate Parentheses

Problem:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution:

ONE

Recursive DFS backtracking.

/**
 * @param {number} n
 * @return {string[]}
 */
let generateParenthesis = function (n) {
    const result = [];
    if (n > 0) {
        dfs(n, 0, 0, '', result);
    }
    return result;
};

function dfs(n, nopen, nclose, path, result) {
    if (path.length === n * 2) {
        result.push(path);
        return;
    }

    if (nopen < n) {
        dfs(n, nopen + 1, nclose, path + '(', result);
    }

    if (nclose < nopen) {
        dfs(n, nopen, nclose + 1, path + ')', result);
    }
}

TWO

BFS.

/**
 * @param {number} n
 * @return {string[]}
 */
let generateParenthesis = function (n) {
    if (n <= 0) {
        return [];
    }

    const queue = [
        {
            path: '(',
            open: 1,
            close: 0
        }
    ];

    while (true) {
        const { path, open, close } = queue.shift();
        if (open + close === n * 2) {
            queue.unshift({ path, open, close });
            break;
        }

        if (open < n) {
            queue.push({
                path: path + '(',
                open: open + 1,
                close
            });
        }

        if (close < open) {
            queue.push({
                path: path + ')',
                open,
                close: close + 1
            });
        }
    }

    return queue.map((x) => x.path);
};

☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆

☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆