LeetCode 022 Generate Parentheses

题目描述：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:

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

分析：

递归

代码如下：

class Solution {

private:

    vector<string> ret;

public:

    void solve(int dep, int maxDep, int leftNum, int leftNumTotal, string s)

    {

        //如果(个数超出，return

        if (leftNumTotal * 2 > maxDep)

            return;

        //如果长度足够，return

        if (dep == maxDep){

            ret.push_back(s);

            return;

        }

        for(int i = 0; i < 2; i++)

            //加 (

            if (i == 0)

                solve(dep + 1, maxDep, leftNum + 1, leftNumTotal + 1, s + '(');

            //加 )

            else if (leftNum > 0)

                solve(dep + 1, maxDep, leftNum - 1, leftNumTotal, s + ')');

    }

    vector<string> generateParenthesis(int n){

        ret.clear();

        solve(0, 2 * n, 0, 0, "");

        return ret;

    }

};

Java：

    public List<String> generateParenthesis(int n) {

        ArrayList<String> result = new ArrayList<String>();

        dfs(result, "", n, n);

        return result;

    }

    public void dfs(ArrayList<String> result, String s, int left, int right) {

        if (left > right) {

            return;

        }

        if (left == 0 && right == 0) {

            result.add(s);

            return;

        }

        if (left > 0) {

            dfs(result, s + "(", left - 1, right);

        }

        if (right > 0) {

            dfs(result, s + ")", left, right - 1);

        }

    }

巴特西

LeetCode 022 Generate Parentheses

最新文章

热门文章