Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Hi, I’m the front watermelon guy, and today we’re going to look at a backtracking problem.

Finding all legal combinations of n pairs of parentheses requires returning an array of strings. For example, if n is 3, return:

[
  "((()))"."() () ()"."() () ()"."() () ()"."() () ()"
]
Copy the code

Code implementation

The idea is to backtrack, the characteristics of the topic is also more obvious.

Let’s look at the code implementation first.

function generateParenthesis(n: number) :string[] {
  const arr: string[] = [];
  r(arr, ' ', n, n);
  return arr;
};

// leftRem: left number of left parentheses
// rightRem: the number left in the right parenthesis
function r(arr: string[], str: string, leftRem: number, rightRem: number) {
  // The left parenthesis usage exceeds n
  // It is illegal to use more closing parentheses than opening parentheses.
  if (leftRem < 0 || rightRem < leftRem) return;
  if (leftRem === 0 && rightRem === 0) {
    arr.push(str);
    return;
  }
  r(arr, str + '(', leftRem - 1, rightRem);
  r(arr, str + ') ', leftRem, rightRem - 1);
}
Copy the code

Here’s how backtracking works.

Backtracking is like when we come to a fork in the road, we choose one road to go, and then we can go back to the current fork in the road and take another road. At the end of the fork road, we return to the last fork road until all roads are gone.

As you can see, backtracking is essentially exhaustive.

N pairs of parentheses and similarly, we’re going to have n forks in the road, and at each fork in the road, we have two choices, are we going to choose the left parenthesis or the right parenthesis.

r(arr, str + '(', leftRem - 1, rightRem);
r(arr, str + ') ', leftRem, rightRem - 1);
Copy the code

But there are two ways we can get an illegal combination:

  1. The number of left parentheses used exceeds N;
  2. When adding parentheses, the number of close parentheses must not exceed the number of open parentheses. If it does, then at least one of the left parentheses has no object, which is illegal.

There is also a case where the number of closing parentheses exceeds n, but this can be derived from a combination of the two cases above, so I won’t discuss it.

The figure below shows the backtracking process when n = 2, where the orange cross represents case 1 and the Red Cross represents case 2.

When these two situations occur, it means that the road is blocked and there is no need to continue recursively, so return directly.

if (leftRem < 0 || rightRem < leftRem) return;
Copy the code

We also need to know when the STR string becomes a legal combination.

It can be leftRem and rightRem are both 0, it can be STR of length N. But we skipped the n, so let’s go with the former.

if (leftRem === 0 && rightRem === 0) {
  arr.push(str);
  return;
}
Copy the code

At the end

Find all legal combinations of n pairs of parentheses, the solution is backtracking. Each time an open or close parenthesis is selected to proceed to the next stage, updating the corresponding states (minus the remaining number by one).

These states will be used in subsequent backtracking to determine whether it is legitimate or not, ending the recursion at a specific time.

I am front-end watermelon brother, welcome to pay attention to me.