题目

image.png

思路

  • 思路一：我们直接使用深度优先暴力每种可能性，定义recur(String s, int l, int r)，当前通过(和)产生的组合，l表示剩余未使用(，r表示剩余未使用)，再加上判断剪枝掉不合理，判断条件是先使用左括号后使用右括号，因此每次递归时，必然左括号要小于等于右括号。结束条件是左右括号都使用完成即可。
  • 思路二：我们知道每次(n,n)的组合依赖于(n-1,n-1)的组合，因此当我们知道(n-1,n-1)的组合，再遍历它的每个人结果进行组合，组合有2种或3种可能性：
    1. “(“ + s + “)
    2. “()” + s
    3. s + “()”

其中b、c可能会重复，因此我们要判断一下是否重复再添加，当(1,1)时，我们知道此时只有一种组合就是”()”这就是终止条件，错误解法，哭唧唧

代码

  1.     //1.深度优先+剪枝
  2.     List<String> res = new ArrayList<>();
  3.     public List<String> generateParenthesis(int n) {
  4.         recur("", n, n);
  5.         return res;
  6.     }
  8.     public void recur(String s, int l, int r) {
  9.         if (l == 0 && r == 0) res.add(s);
  10.         if (l < 0 || r < 0 || r < l) return;
  11.         recur(s + "(", l - 1, r);
  12.         recur(s + ")", l, r - 1);
  13.     }
  15.     //2. 动态规划，使用一维数组表示
  16.     public List<String> generateParenthesis(int n) {
  17.         List<String> dp = new ArrayList<>();
  18.         List<String> updateDp = new ArrayList<>();
  19.         dp.add("");
  20.         if (n > 0) dp.set(0, "()");
  21.         for (int i = 2; i <= n; i++) {
  22.             for (String s : dp) {
  23.                 updateDp.add("(" + s + ")");
  24.                 String s1 = s + "()", s2 = "()" + s;
  25.                 updateDp.add(s1);
  26.                 if (!s1.equals(s2)) updateDp.add(s2);
  27.             }
  28.             List<String> t = updateDp;
  29.             updateDp = dp;
  30.             dp = t;
  31.             updateDp.clear();
  32.         }
  33.         return dp;
  34.     }
  37.     //3.暴力递归产生合理括号
  38.     public List<String> generateParenthesis(int n) {
  39.         if (n == 0) {
  40.             List<String> res = new ArrayList<>(); 
  41.             res.add("");
  42.             return res;
  43.         }
  44.         if (n == 1) {
  45.             List<String> res = new ArrayList<>(); 
  46.             res.add("()");
  47.             return res;
  48.         }
  49.         List<String> list =  generateParenthesis(n - 1);
  50.         for (int i = list.size() - 1; i >= 0; i--) {
  51.             String s = list.remove(i);
  52.             list.add("(" + s + ")");
  53.             String s1 = s + "()", s2 = "()" + s;
  54.             list.add(s1);
  55.             if (!s1.equals(s2)) list.add(s2);
  56.         }
  57.         return list;
  58.     }

括号生成