LeetCode_Medium_22. Generate Parentheses

2019.1.31

题目描述:

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,求输出所有可能的括号组合,而且必须是有效的,也就是()的形式,不能出现)(的情况。

解法一:

像这种求出所有可能情况的题目,优先考虑DFS。我们设置两个变量left和right均为n,因为我们知道左括号的数目肯定是大于等于右括号的数目,所以若是left>right那么就直接返回退出当前递归层,若是left=right=0的时候,就表明递归结束,将结果返回,除了这两种情况,则均递归,同时相应left或right减一。

C++代码:

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        generateParenthesisDFS(n,n,"",res);
        return res;
    }
    void generateParenthesisDFS(int left,int right,string out,vector<string> &res){
        if(left==0&&right==0) res.push_back(out);
        if(left>right) return;
        else{
            if(left>0) generateParenthesisDFS(left-1,right,out+'(',res);
            if(right>0) generateParenthesisDFS(left,right-1,out+')',res);
        }
    }
};

解法二:官方解法

暴力法:

LeetCode_Medium_22. Generate Parentheses

Java代码:

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }

    public void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (valid(current))
                result.add(new String(current));
        } else {
            current[pos] = '(';
            generateAll(current, pos+1, result);
            current[pos] = ')';
            generateAll(current, pos+1, result);
        }
    }

    public boolean valid(char[] current) {
        int balance = 0;
        for (char c: current) {
            if (c == '(') balance++;
            else balance--;
            if (balance < 0) return false;
        }
        return (balance == 0);
    }
}

LeetCode_Medium_22. Generate Parentheses

 

解法三:官方解法

就是解法一

Java代码:

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        backtrack(ans, "", 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, String cur, int open, int close, int max){
        if (cur.length() == max * 2) {
            ans.add(cur);
            return;
        }

        if (open < max)
            backtrack(ans, cur+"(", open+1, close, max);
        if (close < open)
            backtrack(ans, cur+")", open, close+1, max);
    }
}

LeetCode_Medium_22. Generate Parentheses

 

解法四:官方解法

LeetCode_Medium_22. Generate Parentheses

Java代码:

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        if (n == 0) {
            ans.add("");
        } else {
            for (int c = 0; c < n; ++c)
                for (String left: generateParenthesis(c))
                    for (String right: generateParenthesis(n-1-c))
                        ans.add("(" + left + ")" + right);
        }
        return ans;
    }
}

LeetCode_Medium_22. Generate Parentheses