Leetcode: Generate Parentheses

布满荆棘的人生 2022-08-07 13:49 15阅读 0赞

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

“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

思路分析：  
最后的组合结果总有这样的规律：左括号的个数大于等于右括号的个数。所以，按照这个规律：假设在位置k剩余left个左括号和right个右括号，如果left>0，可以直接打印左括号。，如果left<right且right!=0，则可以打印右括号。如果left和right均为零，则说明已经完成一个合法排列，可以将其打印出来。

C++参考代码：

class Solution
    {
    private:
        void generateSub(vector<string> &result, string current, int left, int right)
        {
            if (left == 0 && right == 0) result.push_back(current);
            else
            {
                if (left != 0) generateSub(result, current + '(', left - 1, right);
                if (left < right && right != 0) generateSub(result, current + ')', left, right - 1);
            }
        }
    
    public:
        vector<string> generateParenthesis(int n)
        {
            vector<string> result;
            if (n > 0) generateSub(result, string(), n, n);
            return result;
        }
    };

C\#参考代码：

public class Solution
    {
        private void GenerateSubString(IList<string> result, string current, int left, int right)
        {
            String value = current;
            if (left == 0 && right == 0) result.Add(value);
            else
            {
    
                if (left != 0) GenerateSubString(result, current + '(', left - 1, right);
                if (left < right && right != 0) GenerateSubString(result, current + ')', left, right - 1);
            }
        }
    
        public IList<string> GenerateParenthesis(int n)
        {
            IList<string> result = new List<string>();
            if (n > 0) GenerateSubString(result, "", n, n);
            return result;
        }
    }