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. class Solution {
  4. public:
  5.     vector<string> generateParenthesis(int n) {
  6.         vector<string> result;
  7.         string path;
  8.         if (n > 0) generate(n, path, result, 0, 0);
  9.         return result;
  10.     }
  11.     // l 表示 ( 出现的次数, r 表示 ) 出现的次数
  12.     void generate(int n, string& path, vector<string> &result, int l, int r) {
  13.         if (l == n) {
  14.             string s(path);
  15.             result.push_back(s.append(n - r, ')'));
  16.             return;
  17.         }
  19.         path.push_back('(');
  20.         generate(n, path, result, l + 1, r);
  21.         path.pop_back();
  23.         if (l > r) {
  24.             path.push_back(')');
  25.             generate(n, path, result, l, r + 1);
  26.             path.pop_back();
  27.         }
  28.     }
  29. };

代码2

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

  1. // Generate Parentheses
  2. // @author 连城 (http://weibo.com/lianchengzju)
  3. class Solution {
  4. public:
  5.     vector<string> generateParenthesis (int n) {
  6.         if (n == 0) return vector<string>(1, "");
  7.         if (n == 1) return vector<string> (1, "()");
  8.         vector<string> result;
  10.         for (int i = 0; i < n; ++i)
  11.             for (auto inner : generateParenthesis (i))
  12.                 for (auto outer : generateParenthesis (n - 1 - i))
  13.                     result.push_back ("(" + inner + ")" + outer);
  15.         return result;
  16.     }
  17. };

相关题目

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