Generate Parentheses

题目

[22] Generate Parentheses  

https://leetcode.com/problems/generate-parentheses/description/

* algorithms
* Medium (56.57%)
* Total Accepted:    386.8K
* Total Submissions: 680.5K
* Testcase Example:  '3'


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:


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

错误的漩涡

乍看这个题目，决定用递归解决。自己思考了一下，大概就是假设已经有生成的generateParenthesis(n-1)的结果，然后我们对所有的结果进行组合，大概有

"("+generateParenthesis(n-1)+")"
"()"+generateParenthesis(n-1)
generateParenthesis(n-1)+"()"

的形式。然后组成一个递归，当n=1的时候返回["()"]。

提交结果，大错特错。比如，当n=3的时候，我们怎么样都无法获得类似(()())的形式。

正确的思考方法

其实正确的思考方法，想得到就是想得到，想不到就是背下来。

1. 当”(“数小于n的时候，可以继续添加”(“

2. 当”)”的个数小于”(“的个数的时候，可以添加”)”

于是我们可以新建一个方法来记录当前的结果，以及左右括号的计数，然后进行递归。

# @param {Integer} n
# @return {String[]}
def generate_parenthesis(n)
  stack = []
  generate(n,0,0,"",stack)
  return stack
end

def generate(n, left, right, current, stack)
  if left == n && right == n
    stack << current
  end
  if left < n
    generate(n, left+1, right, current+"(", stack)
  end
  if right < left
    generate(n, left, right+1, current+")", stack)
  end
end

插曲

在翻看答案的时候，第一眼看到了下面的解答。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> allComb;
        string comb;
        findParenthesis(n, 0, 0, comb, allComb);
        return allComb;
    }
    
    void findParenthesis(int n, int nleft, int nright, string &comb, vector<string> &allComb) {
        if(nleft==n && nright==n) {
            allComb.push_back(comb);
            return;
        }
        
        if(nleft<n) {
            comb.push_back('(');
            findParenthesis(n, nleft+1, nright, comb, allComb);
            comb.pop_back();
        }
        
        if(nright<nleft) {
            comb.push_back(')');
            findParenthesis(n, nleft, nright+1, comb, allComb);
            comb.pop_back();
        }
    }
};

然后我陷入了沉思，最后的comb.pop_back()是为什么？
对比正解，我们发现我们在递归的时候改变了重复带入的变量的值，所以在下一次迭代之前，应该把它恢复。
至于为什么要恢复。。。撒。