This is the 19th day of my participation in the Genwen Challenge

Topic describes

Parentheses generates

The number n represents the logarithm of parentheses generated. Design a function that generates all possible and valid parentheses combinations. Leetcode-cn.com/problems/ge…

/ / sample 1Enter n =3Output:"((()))"."() () ()"."() () ()"."() () ()"."() () ()"]
/ / sample 2Enter n =1Output:"()"]
Copy the code

The label

DFS recursive

Analysis of the problem solving

1. The recursion

Let’s get right to it.

This problem is very troublesome and should be easy. I'm just going to recursively generate all possible combinations of parentheses based on the n that I pass in, which is to generate parentheses logarithms. I can do this with DFS backtracking recursion that I used before, but as I started to work on the problem I found that backtracking recursion was a good way to go back to all possible problems. The first time you enter a recursive function, you must generate the first close parenthesis (. The second time you go into the recursive function, there are two possibilities, (and) two ways. And then it bifurcates,1
                         (
          2                            3
          ()                           ((

 4                 5           6                  7() () () () (((here we need to judge, if right parenthesis is larger than the left parenthesis, to match, idea that is not the first5A recursive function needs to return to stop running. This is done each time recursively until the number of left and right parentheses equals the number of passed n, the generated logarithm of parentheses, pushing the currently generated string of parentheses into the result. When all the recursive functions are done, we get the result of our response.Copy the code

Go to ！！！！！

function generateParenthesis(n: number) :string[] {
    const result:string [] = []
    const dfs = (path: string, count1: number, count2: number) = > {
        // Path is a recursive string, count1 is the number of open parentheses, count2 is the number of close parentheses
        // When the parenthesis is greater than n, the age after the parenthesis is generated, the recursive function will not run.
        if(count1 > n || count2 > n) return
        // If the number of close parentheses is greater than the number of open parentheses, then the number of close parentheses is greater than the number of open parentheses.
        if(count2 > count1) return 
        // We have the right number of open parentheses and right parentheses so we can deduce the correct result
        if(count1 === n && count2 === n) {
            result.push(path)
            return 
        }

        // This handles the first pass of an empty string
        if(count1 === 0) {
            dfs(path + '(', count1 + 1, count2)
        }
        else {
            // There are only two results
            dfs(path + '(', count1 + 1, count2)
            dfs(path + ') ', count1, count2 + 1)
        }
    }
    dfs(' '.0.0)
    return result
};

Copy the code

The last

From today on, an algorithm problem and publish articles every day, first want to solve the problem group for Top100, the eleventh topic finished work!!