describe

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is: 

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

Train of thought

You can use a recursive approach for the generation of repeated content sequences. The generated parenthesis part can be recursed, and the specific recursion process is shown as follows: Figure Source



As shown in the figure, recursive exit needs to be designed for recursion. In this problem, exit is that the number of close parentheses exceeds the number of open parentheses (illegal case), and the number of left parentheses equals the number of right parentheses equals 0 (legal case, join the output queue). Other cases can be treated as an intermediate process.

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new LinkedList<String>();
        // The beginning of recursion
        add(n, n, "", result);
        return result;
    }
    
    // The first two integers are the remaining parentheses, current is the current combination, and result is the result set
    public void add(int left, int right, String current, List<String> result){
        // If the number of left parentheses is greater than the number of left parentheses, the current condition is illegal
        if(left > right){
            return;
        }
        // Complete legal case, left and right parenthesis combination complete
        if(left == 0 && right == 0){
            result.add(current);
            return;
        }
        // When the left and right parentheses are not 0, try adding the left and right parentheses separately
        if(left > 0){
            add(left-1, right, current+"(", result);
        }
        
        if(right > 0){
            add(left, right-1, current+")", result); }}}Copy the code
Submissions in Java online submission for generating Parentheses.
Memory Usage: 39.8 MB, less than 17.42% of Java online submissions for generating Parentheses.

The key to the solution lies in the process of converting the idea of exhaustive thinking into recursive thinking. That’s one way of doing it.