22. 括号生成

image.png

  1. import java.util.ArrayList;
  2. import java.util.List;
  4. public class Solution {
  6.     // 方法 2：用加法
  8.     public List<String> generateParenthesis(int n) {
  9.         List<String> res = new ArrayList<>();
  10.         // 特判
  11.         if (n == 0) {
  12.             return res;
  13.         }
  15.         // 这里的 dfs 是隐式回溯
  16.         dfs("", 0, 0, n, res);
  17.         return res;
  18.     }
  20.     /**
  21.      * @param curStr 当前递归得到的结果
  22.      * @param left   左括号用了几个
  23.      * @param right  右括号用了几个
  24.      * @param n      左括号、右括号一共用几个
  25.      * @param res    结果集
  26.      */
  27.     private void dfs(String curStr, int left, int right, int n, List<String> res) {
  28.         // 因为是递归函数，所以先写递归终止条件
  29.         if (left == n && right == n) {
  30.             res.add(curStr);
  31.             return;
  32.         }
  34.         // 如果左括号还没凑够，继续凑
  35.         if (left < n) {
  36.             // 拼接上一个左括号，并且剩余的左括号个数减 1
  37.             dfs(curStr + "(", left + 1, right, n, res);
  38.         }
  39.         // 什么时候可以用右边？例如，(((((()，此时 left > right，
  40.         // 不能用等号，因为只有先拼了左括号，才能拼上右括号
  41.         if (right < n && left > right) {
  42.             // 拼接上一个右括号，并且剩余的右括号个数减 1
  43.             dfs(curStr + ")", left, right + 1, n, res);
  44.         }
  45.     }
  47.     public static void main(String[] args) {
  48.         Solution2 solution2 = new Solution2();
  49.         List<String> res = solution2.generateParenthesis(3);
  50.         System.out.println(res);
  51.     }
  52. }

参考

https://juejin.im/post/5b3b56045188251abe49f738
https://leetcode-cn.com/problems/permutations/solution/hua-chu-di-gui-shu-che-di-li-jie-dfshui-su-by-nora/