LeetCode22-括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

一、思路

（一）迭代

首先考虑，n个括号，有多少种合理的生成方法，分析几个简单的例子：

n=1时

"()"	

n=2时

"(())"	
"()()"	

n=3时

  "((()))"
  "(()())"
  
  "(())()"
  "()()()"

  "()(())"
  "()()()"	重复

可以看出，这个生成方法就是不断迭代的过程，
生成n=k个有效括号的组合过程如下：
先生成k-1的组合，然后：
（1）在k-1的组合最外层，添加括号
（2）在k-1的组合最左边，添加括号
（3）在k-1的组合最右边，添加括号
这里（2）和（3）会有一个重复，要减去

因此，设$f(n)$f(n)为n个括号的组合数量，则有：
$f(n)=3f(n-1)-1$f(n)=3f(n−1)−1且$f(1)=1, f(2)=2$f(1)=1,f(2)=2
根据初始条件，解得：$f(n)=\frac {3^{n-1}-1}{2}$f(n)=23n−1−1​

根据这个想法写出来的代码不通过。解答错误，原因在于，存在部分重复，以及不是所有的k阶括号都是由k-1阶括号衍生出来的
例如：n=4

  "(((())))"
  "((()()))"  
  "((())())"  
  "(()(()))"  
  "(()()())"  
  
  "((()))()"
  "(()())()"
  "(())()()"
  "()(())()"		重复
  "()()()()"		重复
  
  "()((()))"
  "()(()())"
  "()(())()"		重复
  "()()(())"
  "()()()()"		重复
  另外这个括号没办法根据之前法则生成
  "(())(())"

（二）回溯法

因为这个题目的形式，和枚举很像，因此是否能够通过回溯算法解决呢？
n=k时，需要将’(‘和’)‘放入2k个位置中，第一个位置放入的一定是’(’，最后一个位置一定是’)’，我们只需考虑中间的放置情况即可，每次放置，可能有两种方法，一种是放’(’，另一种是放’)’。

C++代码：

class Solution {
public:
	vector<string> parenthesis;
	map<int, string> hashtable;

	vector<string> generateParenthesis(int n) {
		if (n == 0)
			return parenthesis;

		hashtable.insert(map<int, string>::value_type(1, "("));
		hashtable.insert(map<int, string>::value_type(0, ")"));

		string s = "(";
		gParenthesis(n, 2, 1, 1, s);
		return parenthesis;
	}

	void gParenthesis(int n, int m, int nums_left, int nums, string s) {
		
		if (2*n == m) {
			s = s + ")";
			nums_left--;
			if (nums_left == 0)
				parenthesis.push_back(s);
			return;
		}

		for (int i = 0; i < 2; i++)	{
			if (nums_left == 0) {
				s += "(";
				gParenthesis(n, m + 1, 1, nums + 1, s);
				break;
			}
			else {
				if (nums < n) {
					s += hashtable[i];
					if (i)
						gParenthesis(n, m + 1, nums_left + 1, nums + 1, s);
					else
						gParenthesis(n, m + 1, nums_left - 1, nums, s);
					s.pop_back();
				}
				else {
					s += ")";
					gParenthesis(n, m + 1, nums_left - 1, nums, s);
					break;
				}
			}
		}
	}
};

执行效率：