先上代码

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中。

注意事项：

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