This is the 22nd day of my participation in the August Wen Challenge.More challenges in August

The title

The number n represents the logarithm of parentheses generated. Design a function that generates all possible and valid parentheses combinations.

The combination of valid brackets must meet the following requirements: The left bracket must be closed in the correct sequence.

 

Example 1:

Enter n = 3

Output: [” ((())) “, “() () ()”, “() () ()”, “() () ()”, “() () ()”]

Example 2:

Enter n = 1

Output: [” () “]

 

Tip:

  • 1 <= n <= 8

Their thinking

Idea 1

I’m going to keep choosing parentheses, either open parentheses or close parentheses.

And, there are constraints:

  • As long as(If there’s any left, you can choose(.(((((That’s not even illegal yet.
  • When the rest of the)than(A long time before you can choose), otherwise,)You can’t. If you do, it’s illegal (see below).

The state of the node is described as: the string currently constructed, and the number of left parentheses.

Go back and make three important points

  • choose
    • Here, at most two choices at a time, open parenthesis, or close parenthesis, “select” opens up a spatial tree of solutions.
    • DFS traverses the tree to find all the solutions, a process called backtracking.
  • The constraint
    • That is, when you can choose an open parenthesis, and when you can choose a close parenthesis.
    • Use constraints to “prune,” that is, remove options that do not produce a solution, that is, cut branches that do not lead to a legitimate solution.

      • For example, if () is left with one parenthesis left and one parenthesis left, then () becomes ()), this is the wrong choice and cannot be made an option (without falling into recursion) :

        ‘if (right > left) {// If (right > left)

      dfs(str + ‘)’, left, right – 1); } `

  • The target
    • Builds a valid parenthesis string with n pairs of parentheses exhausted.
    • This means that when the length of the build reaches 2*n, you can end the recursion (without continuing the selection).

The benefits of adequate pruning

So with enough pruning, all the options that don’t go to the legal solution, they get killed, and if you recurse down, they all go to the legal solution. That is, as long as the recursion: when the length of the constructed string is 2*n, a legal solution is generated and added to the solution set.

code

var generateParenthesis = function (n) {
  const res = [];

  const dfs = (lRemain, rRemain, str) = > { // The number of left parentheses, STR is the currently constructed string
    if (str.length == 2 * n) { // String construction is complete
      res.push(str);           // Add the solution set
      return;                  // End the current recursive branch
    }
    if (lRemain > 0) {         // As long as the left parenthesis is left, you can select it and continue with the selection (recursion)
      dfs(lRemain - 1, rRemain, str + "(");
    }
    if (lRemain < rRemain) {   // Select the right parenthesis if there is more left than left parenthesis
      dfs(lRemain, rRemain - 1, str + ")"); // Then proceed with the selection (recursion)}}; dfs(n, n,""); // Recursive entry, the remaining number is n, the initial string is an empty string
  return res;
};
Copy the code

Idea 2

Before studying backtracking algorithms, you should be familiar with tree DFS, because backtracking problems can be abstracted into tree structure problems

You find it difficult to backtrack because your tree structure and its algorithm are unfamiliar

For those unfamiliar with tree DFS, or for a comprehensive and systematic study of backtracking, greed, and dynamic programming, see here: Building knowledge systems for Data structures and algorithms

The problem is abstracted into a tree structure traversal problem

Code:

`var generateParenthesis = function(n) { const res = [] if (n <= 0) return res

const dfs = (path, open, close) => {
    if (open > n || close > open) return
    if (path.length == 2 * n) {
        res.push(path)
        return
    }
    dfs(path + "(", open + 1, close)
    dfs(path + ")", open, close + 1)
}

dfs("", 0, 0)
return res
Copy the code

}; `

The last

I dreamed of traveling with swords

Look at the prosperity of the world

Young heart always some frivolous

Just a man after all

No regrets I go my way

“Front-end brush” No.22