解法一：DFS

合法的括号顺序要保证每次添加新括号都满足左括号数量大于右括号，因此根据当前左右括号数量来决定下一步递归可以添加哪种括号。

  1. import java.util.LinkedList;
  2. import java.util.List;
  4. class Solution {
  5.     public List<String> generateParenthesis(int n) {
  6.         List<String> ans = new LinkedList<>();
  7.         dfs(n, n, ans, new StringBuilder());
  8.         return ans;
  9.     }
  11.     /**
  12.      * @param left  当前还可以添加的左括号数量
  13.      * @param right 当前还可以添加的右括号数量
  14.      * @param ans   答案数组
  15.      * @param str   当前字符串
  16.      */
  17.     private void dfs(int left, int right, List<String> ans, StringBuilder str) {
  18.         if ((left == 0) && (right == 0)) {
  19.             ans.add(str.toString());
  20.             return;
  21.         }
  22.         if (left == 0) {
  23.             dfs(left, right - 1, ans, str.append(')'));
  24.             str.deleteCharAt(str.length() - 1);
  25.         } else if (left == right) {
  26.             dfs(left - 1, right, ans, str.append('('));
  27.             str.deleteCharAt(str.length() - 1);
  28.         } else if (left < right) {
  29.             dfs(left - 1, right, ans, str.append('('));
  30.             str.deleteCharAt(str.length() - 1);
  31.             dfs(left, right - 1, ans, str.append(')'));
  32.             str.deleteCharAt(str.length() - 1);
  33.         }
  34.     }
  35. }