Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

22. Parenthesis generation

Topic, given a n, generate n effective arrangement of brackets, for example given n is 3, the effective arrangement is: [” ((())) “, “() () ()”, “() () ()”, “() () ()”, “() () ()”].

Usually such permutation and combination problems can be completed using recursion and depth-first traversal, first write out the recursive shelf:

void dfs(a) {
    // The termination condition for recursion, i.e., under what circumstances are recursive calls not made
    
    // Process the logic of the current layer
    
    // Make the next recursive call
    
    // Restore the recursive call money state if necessary
}
Copy the code

Then, we need two variables:

  • A list to hold the result set
  • A StringBuffer is used to concatenate each possible result
class Solution {
    List<String> result = new ArrayList<>();
    StringBuffer sb = new StringBuffer();
    public List<String> generateParenthesis(int n) {
        dfs(0.0, n);
        return result;
    }

    private void dfs(a) {
        // The termination condition for recursion, i.e., under what circumstances are recursive calls not made
    
        // Process the logic of the current layer

        // Make the next recursive call

        // Restore the recursive call money state if necessary}}Copy the code

Next, deal with the logic in the DFS method. The key here is how to generate an effective parenthesis arrangement that meets the following conditions:

  • If the number of left parentheses already arranged is less than n, you can append the left parentheses, that is, you can append the left parentheses at any time as long as the left parentheses are not running out
  • If there are fewer close parentheses already arranged than in expansions, you can append close parentheses, which are pairs of parentheses, with the opening parentheses appearing more closely than the closing parentheses.

Meet the above two conditions on it.

Final code:

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

    private void dfs(int l, int r, int n) {
        // The termination condition for recursion, i.e., under what circumstances are recursive calls not made
        // The recursion ends when the result is twice as long as the number of parentheses
        if (sb.length() == n * 2) {
            result.add(sb.toString());
            return;
        }
        
        // If any of the above conditions are met, the corresponding parentheses can be appended
        // After the recursive call, the appended parentheses are removed
        
        if (l < n) {
            // Process the logic of the current layer
            sb.append('(');
            // Make the next recursive call
            dfs(l + 1, r, n);
            // Restore the recursive call money state if necessary
            sb.deleteCharAt(sb.length() - 1);
        }
        if (r < l) {
            // Process the logic of the current layer
            sb.append(') ');
            // Make the next recursive call
            dfs(l, r + 1, n);
            // Restore the recursive call money state if necessary
            sb.deleteCharAt(sb.length() - 1); }}}Copy the code