Generate Parentheses

描述

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

  1. "((()))", "(()())", "(())()", "()(())", "()()()"

分析

小括号串是一个递归结构，跟单链表、二叉树等递归结构一样，首先想到用递归。

一步步构造字符串。当左括号出现次数<n时，就可以放置新的左括号。当右括号出现次数小于左括号出现次数时，就可以放置新的右括号。

代码1

  1. // Generate Parentheses
  2. // 时间复杂度O(TODO)，空间复杂度O(n)
  3. public class Solution {
  4.     public List<String> generateParenthesis(int n) {
  5.         List<String> result = new ArrayList<>();
  6.         StringBuilder path = new StringBuilder();
  7.         if (n > 0) generate(n, path, result, 0, 0);
  8.         return result;
  9.     }
  10.     // l 表示 ( 出现的次数, r 表示 ) 出现的次数
  11.     private static void generate(int n, StringBuilder path,
  12.                                  List<String> result, int l, int r) {
  13.         if (l == n) {
  14.             StringBuilder sb = new StringBuilder(path);
  15.             for (int i = 0; i < n - r; ++i) sb.append(')');
  16.             result.add(sb.toString());
  17.             return;
  18.         }
  20.         path.append('(');
  21.         generate(n, path, result, l + 1, r);
  22.         path.deleteCharAt(path.length() - 1);
  24.         if (l > r) {
  25.             path.append(')');
  26.             generate(n, path, result, l, r + 1);
  27.             path.deleteCharAt(path.length() - 1);
  28.         }
  29.     }
  30. }

代码2

另一种递归写法，更加简洁。

  1. // Generate Parentheses
  2. // @author 连城 (http://weibo.com/lianchengzju)
  3. public class Solution {
  4.     public List<String> generateParenthesis(int n) {
  5.         if (n == 0) return new ArrayList<>(Arrays.asList(""));
  6.         if (n == 1) return new ArrayList<>(Arrays.asList("()"));
  7.         List<String> result = new ArrayList<>();
  9.         for (int i = 0; i < n; ++i)
  10.             for (String inner : generateParenthesis (i))
  11.                 for (String outer : generateParenthesis (n - 1 - i))
  12.                     result.add ("(" + inner + ")" + outer);
  14.         return result;
  15.     }
  16. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/dfs/generate-parentheses.html