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

preface

Force buckle question 22 parentheses generated as follows:

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

Example 1:

Input: n = 3 output: [” ((())) “, “() () ()”, “() () ()”, “() () ()”, “() () ()”]

Example 2:

Output: [“()”]

Tip:

  • 1 <= n <= 8

A, thinking

There are two ways to do this, violence and backtracking

Brute force

Exhaustive method: Enumerate all permutations, then exclude invalid parentheses

For example, if n = 3, there are 2^2*n, that is, 2^6 positions (each position has two possible positions: open parenthesis or close parenthesis)

Backtracking (proper pruning)

You can think of generating parentheses as traversing a tree (a full binary tree of depth N, with each node having two children down from the root).

So the question becomes, how do we reasonably traverse the tree? It’s actually quite simple, since we want to form valid parentheses, we just have to exclude non-valid parentheses.

To ensure that a valid parenthesis is generated, only two things need to be done:

  1. If the number of open brackets must be less than N, add an open bracket
  2. If the number of close parentheses is smaller than that of open parentheses, you can add close parentheses

Take N=4 as an example, with eight empty positions, add parentheses from left to right. Just make sure that the last parentheses are valid. Why is that? This effectively eliminates the possibility that the closing parenthesis comes first and the number of left and right parentheses is inconsistent

Graphical backtracking (Proper pruning)

In this example, if N is 2, there are four positions that can be filled. Left: number of left children selected. Right: number of right children selected

A complete binary tree with N = 2 and depth of 4 looks like this:

Throughout, choose the left child first

Starting from the root node, select the left child first and select the left child twice as follows:

Continue down to find left = 3, left > 2, at this time will prune. After pruning, it looks like this:

Then select the right child of the current node, as shown below:

If you continue down, you will find left = 3 and left > 2. At this point, you will prune again. After pruning, it looks like this:

Then select the right child of the current node, and the first correct result (()) is obtained, as shown below:

Back up, select the second node at depth = 2. As follows:

Further down, the second correct result ()() can be obtained. The results and pruning are shown below:

Further back up, the second node at depth=1 needs pruning. Left = 0, right = 1, right > left needs pruning. As shown below:

This is the proper pruning in the process of backtracking. You should be able to understand backtracking better with diagrams!

Second, the implementation

Brute force

The implementation code

    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        generateAll(new char[2 * n], 0, result);
        return result;
    }

    /** * recursively generates all combinations and removes all valid parentheses */
    public void generateAll(char[] current, int pos, List<String> result) {
        // End of recursion condition: length 2n
        if (pos == current.length) {
            if (valid(current)) {
                result.add(newString(current)); }}else {
            // The current position is (
            current[pos] = '(';
            generateAll(current, pos + 1, result);
            // The current position is)
            current[pos] = ') ';
            generateAll(current, pos + 1, result); }}/** * If there are more close parentheses than left parentheses during traversal, the parentheses */ are not valid
    public boolean valid(char[] current) {
        int balance = 0;
        for (char c: current) {
            if (c == '(') {
                ++balance;
            } else {
                --balance;
            }
            if (balance < 0) {
                return false; }}return balance == 0;
    }
Copy the code

The test code

    public static void main(String[] args) {
        List<String> result = new Number22().generateParenthesis(2);
        for(String str : result) { System.out.println(str); }}Copy the code

The results of

Backtracking (proper pruning)

The implementation code

Tips: Whether you add an open parenthesis or a close parenthesis, remove it later to ensure that you can trace back correctly

    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        dfs(result, new StringBuilder(), n, 0.0);
        return result;
    }

    /** * backtrace *@paramRet result set *@paramPath Result of the current traversal *@paramN logarithm of parentheses *@paramLeftN Number of left parentheses *@paramRightN Number of close parentheses */
    public void dfs(List<String> ret, StringBuilder path, int n, int leftN, int rightN) {
        if (path.length() == 2 * n) {
            ret.add(path.toString());
            return;
        }
        // If the number of open parentheses is less than n, open parentheses can be added
        if (leftN < n) {
            dfs(ret, path.append("("), n, leftN + 1, rightN);
            // Delete the last element in the path
            path.deleteCharAt(path.length() - 1);
        }
        // If the number of close parentheses is smaller than the number of open parentheses, close parentheses can be added
        if (rightN < leftN) {
            dfs(ret, path.append(")"), n, leftN, rightN + 1);
            // Delete the last element in the path
            path.deleteCharAt(path.length() - 1); }}Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥