Leetcode: Generate Parenthesis

题目:

https://oj.leetcode.com/problems/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:

"((()))", "(()())", "(())()", "()(())", "()()()"

分析:

看到题目的之后, 首先在心里模拟生成结果的过程, 比如说n=2时, 首先 生成一个"(", 然后就有两个选择了, 生成"("或")", 再下一步又面临着两个选择。。。以此类推, 每次都有两个选择, 仿佛生成了一棵二叉树。 

Center

这种情况下, 多半要用递归来解决了。递归算法, 最重要的是两点, 一个是找到它终止的边界条件, 一个是找到它每次递归的规律。

首先是终止条件, 显然这个问题的终止条件是, “(”和")"的数量都达到n时,以及")"的数量增长到和"("的数量相等时, 算法就终止了。它的递归规律是, 每次"("的数量或者")"的数量加1。 然后就可以写代码了。

代码:

class Solution
{
public:
    vector<string> generateParenthesis(int n)
    {
        generate(n, 0, 0, "");

        return res;
    }

    void generate(int n, int left, int right, string s)
    {
        if (right == n)
            res.push_back(s);

        if (left < n)
            generate(n, left + 1, right, s + '(');

        if (right < left)
            generate(n, left, right + 1, s + ')');
    }

private:
    vector<string> res;
};

参考:

http://blog.csdn.net/yutianzuijin/article/details/13161721

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/38642115