content: package question0022_generate_parentheses;
  
  import java.util.ArrayList;
  import java.util.HashMap;
  import java.util.List;
  import java.util.Map;
  
  /**
   * https://leetcode-cn.com/problems/generate-parentheses/
   *
   * 递归实现（用记忆化搜索来优化）。
   *
   * 时间复杂度和空间复杂度的计算比较复杂，略。
   *
   * 执行用时：3ms，击败87.02%。消耗内存：37.4MB，击败86.88%。
   */
  public class Solution3 {
      private Map<Integer, List<String>> dp = new HashMap<>();
  
      public List<String> generateParenthesis(int n) {
          if (dp.containsKey(n)) {
              return dp.get(n);
          }
          List<String> list = new ArrayList<>();
          if (n == 0) {
              list.add("");
          }
          for (int i = 0; i < n; i++) {
              List<String> list1 = generateParenthesis(i), list2 = generateParenthesis(n - i - 1);
              for (String s1 : list1) {
                  for (String s2 : list2) {
                      //写成这样也是可以的：list.add(s1 + "(" + s2 + ")");
                      list.add("(" + s1 + ")" + s2);
                  }
              }
          }
          dp.put(n, list);
          return list;
      }
  }