LeetCode - 22. Generate Parentheses

Thoughts:

I choose backtracking to solve this problem.

because when I visualize the process,

I found that it’s a tree and need to store the track.

The time complexity will be O(2ⁿ),

it’s because the every node has their own decision.

Thoughts visuzlization:

n = 3
openN = 0 (open bracket number in a current string)
closedN = 0 (closed bracket number in a current string)
current = '' (current brackets string)
answer = [] (storing all brackets string)

               (
             (( ()
          ((( (() ()(
    ((() (()( (()) ()(( ()()
  ((()) (()() (())( ()(() ()()(
((())) (()()) (())() ()(()) ()()()

decisions
1. need to fill open bracket at first
2. when the number of open bracket is enough, then fill closed bracket

keep doing recursion and decide which action need to do
and pass all tracking data to the process of every bracket string

the base case is the time every bracket pair in a current brackets string finish
and push the the compeled string to the answer array

Code:

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  const answer = [];
  backtrack(n, 0, 0, '', answer);
  return answer;
};

const backtrack = (n, openN, closedN, curr, answer) => {
  if (n === openN && openN === closedN) {
    answer.push(curr);
    return;
  }
  if (openN < n) {
    backtrack(n, openN + 1, closedN, curr + '(', answer);
  }
  if (closedN < openN) {
    backtrack(n, openN, closedN + 1, curr + ')', answer);
  }
};

Reference

Original link

Tree intro (NTNU)

Backtracking intro (NTNU)