括号生成

题目描述

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

输入输出样例

Input: n = 3
Output: ["((()))","(()())","()(())","()()()"]

题解

对于这个题目需要解决的问题有二：

• 如何确保生成的括号有效
• 如何全部找到且不遗漏

1. 什么样的括号是有效的

• 所有括号都是成对出现的，只有保证成对的出现才是有效括号

2. 如何全部找到且不遗漏

• 首先这是使用暴力破解肯定是行不通的，想要找到全部就只有使用回溯算法。

3. 回溯三部曲：
   1. 确定回溯函数
   • 字符串ans用于收集叶子节点，括号分左(left)右(right),确定生成多少对括号的n,对应的函数签名就可以写出来了

     void backtracking(string ans,int left,int right,int n)

   2. 确定终止条件
   • 当生成了对应的对数的时候，即(left==n && right == n)时，为终止条件
   3. 确定单层遍历逻辑
   • 由于是添加所以不需要横向遍历，但是需要使用递归对其左右进行一个纵向的遍历。
4. 对应的回溯通过树表现出来就是一个二叉树，具体的可通过下图与代码实现进行一个深入的理解

class Solution {
public:
    vector<string> res;
    void backtracking(string ans,int left,int right,int n) {
        //终止条件
        if (left == n && right == n) {
            res.push_back(ans);
            return;
        }

        if (left < right) return;
        if (left < n) backtracking(ans+"(",left+1,right,n);
        if (right < n) backtracking(ans+")",left,right+1,n);
    }
    vector<string> generateParenthesis(int n) {
        res.clear();
        backtracking("",0,0,n);
        return res;
    }
};