Generate Parentheses

LeetCode笔记 阅读(78)

编号 : 22      
难度 : <font color="orange">Medium</font>

# 题目 :  
>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:
>
>```
>[
>  "((()))",
>  "(()())",
>  "(())()",
>  "()(())",
>  "()()()"
>]
>```
>

# 解 :  
```Cpp
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        generate("(", 1, 0, n, ret); // 第一个只能是左括号
        return ret;
    }
    
    /* 递归函数 */
    void generate(string pre, int left, int right, int n, vector<string>& ret) 
    {
        /* 递归结束 */
        if(right == n)
        {
            ret.push_back(pre);
            return;
        }
        
        if(left < n)
        {
            /* 左括号任何时候都可以添加 */
            generate(pre + "(", left + 1, right, n, ret);
        }
        
        if(left > right)
        {
            /* 右括号只能在比左括号少的时候才能添加 */
            generate(pre + ")", left, right + 1, n, ret);
        }
    }
};
```

# 分析 :  
这道题要求生成n对括号组成的所有符合逻辑的字符串。  

为了避免重复,考虑排列组合,每一个位置上可以有`(`和`)`两个选择。

显然,任何时候添加`(`都不会导致字符串最终违法规则,而`)`只有在`(`比`)`多的时候才能添加。

按照上述规则,用两个变量`left`和`right`分别保存已分配的`(`和`)`的个数,`left < n`则添加一个`(`递归,`left > right`则添加一个`)`递归,`right == n`时说明已经分配完,将字符串保存进结果返回。

Markdown使用 帮助


匿名

天真烂漫,无忧无虑。

匿名

安居乐业,日进斗金。

匿名

安居乐业,日进斗金。