括号生成（dfs）1

标题中的“括号生成（dfs）1”是指利用深度优先搜索（DFS）算法解决括号的有效组合问题。这个问题是LeetCode等在线编程平台上的经典题目，主要考察的是递归和回溯策略的理解与应用。 描述中提到，给定一个整数`n`，表示可以生成的括号对数，目标是生成所有可能的且有效的括号组合。有效括号组合指的是左括号 '(' 和右括号 ')' 的匹配关系正确，即每个左括号都有对应的右括号，并且括号内的括号组合也是有效的。 标签“leetcode”表明这是一个在LeetCode网站上可以找到的问题，通常这类问题都是针对算法和数据结构的训练。 以下是对给定代码的详细解释： 1. `generateParenthesis`函数是主函数，接受一个整数`n`作为参数，返回一个字符串向量`res`，其中存储了所有有效括号组合。初始时，`res`为空，`left`和`right`变量分别记录当前已使用的左括号和右括号的数量，它们都初始化为0。 2. `dfs`函数是深度优先搜索的实现，它接受四个参数：结果向量`res`、当前构造的字符串`str`、剩余可添加的括号对数`n`、已使用的左括号数量`l`和已使用的右括号数量`r`。这个函数通过递归调用自身来探索所有可能的括号组合。 3. 在`dfs`函数中，首先检查条件`l<r||l>n||r>n`，如果这些条件满足，说明当前括号组合无效，因为左括号不能多于右括号，且左右括号总数不能超过`n`。 4. 当`l`等于`r`且等于`n`时，说明已经找到了一个有效的括号组合，此时将`str`加入结果向量`res`。 5. 接下来的两行递归调用，分别代表在当前字符串末尾添加一个左括号和一个右括号。每次递归都会改变`l`和`r`的值，从而继续构建新的括号组合。 6. 这种递归方式会按照深度优先的顺序遍历所有可能的路径，直到所有有效括号组合都被找到。 例如，当`n`为3时，可能的括号组合有5种，如描述中的示例1所示： - `"((()))"` - `"(()())"` - `"(())()"` - `"(())()"` - `"()()()"` 当`n`为1时，唯一的有效组合是空字符串，因为只有一个括号对，如示例2所示：`"()"`。 这个问题是通过深度优先搜索和回溯的方法来生成所有可能的括号序列，确保每一种组合都是有效的。这个算法的时间复杂度是O(4^n/n^(3/2))，空间复杂度是O(n)，因为每个有效括号序列都可以看作是一棵树，而DFS在最坏情况下需要访问树的所有节点。