先上代码

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    private ArrayList<String> res;
    public ArrayList<String> generateParenthesis (int n) {
        res = new ArrayList<>();
        recursion(n, n, "");
        return res;
    }

    private void recursion(int left, int right, String s) {
        if(left == 0 && right == 0){
            res.add(s);
        }else{
            if(left > 0){
                recursion(left - 1, right, s + "(");
            }if(right > left){
                recursion(left, right - 1, s + ")");
            }
        }
    }
}

递归思想

对于剩下的left个左括号和right个右括号,判断能在字符串的尾部继续插入括号。插入括号后就将对应的括号个数-1,进行下一轮的递归。

插入条件:

  • left和right必须有一个大于0才能进行插入。
  • 如果left==right说明剩下的左括号数和右括号数相同,则字符串中的左右括号数也相同,那么此时只能将左括号插入至字符串末尾。
  • 如果left<right说明字符串中左括号数大于右括号数,则此时可以插入右括号。
  • 因为保证了先插左括号再插右括号所以此插法不会出现left>right的情况。

终止条件:

left和right都等于0,说明左括号和右括号都被插入完毕,可以将此字符串作为一个结果保存在List中。

注意事项:

输出的组合顺序必须按照题目中给出的例子,否则算错误。