[数据结构与算法]Leetcode | 0022.括号生成

题目

数字?n?代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且?有效的?括号组合。

示例

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

输入：n = 1
输出：["()"]

解决方法

递归：先不考虑结果的有效性，只考虑题目所需要的组合。此时有 n 个 "(" 和 n 个 ")"，有2n个格子，写出所有可能的组合。使用递归的方式来填写这2n个格子。填完一个格子之后，进入下一层递归，考虑下一个格子该填什么。

剪枝：对不合法的分支进行判断，剪去不合法的分支。当遇到两种情况时，应当把该分支剪去：

1、已经使用的左括号数量等于n或者超过n时，该位置不能再放左括号。

2、当已经使用的右括号数量大于等于左括号数量时，该位置不能再放右括号。

代码实现

class Solution {
public:
    vector<string> res;
    void dfs(string temp,int left,int right,int flag,int n){
        if(flag == 2*n){
            res.push_back(temp);
            return;
        }
        if(left < n){
            dfs(temp+"(",left+1,right,flag+1,n);
        }
        if(right < left){
            dfs(temp+")",left,right+1,flag+1,n);
        }
    }
    vector<string> generateParenthesis(int n) {
        string temp;
        dfs(temp,0,0,0,n);
        return res;
    }
};