22. Generate Parentheses

🟠   🔖  字符串 动态规划 回溯  🔗 LeetCode

题目

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1

Output: ["()"]

Constraints:

• 1 <= n <= 8

题目大意

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

解题思路

1. 定义一个空数组 res 用于存储最终结果，以及一个空数组 track 用于存储当前生成的括号组合。
2. 编写回溯函数 backtrack，该函数接收两个参数 left 和 right，分别表示当前已使用的左括号和右括号的数量。
3. 在回溯函数中，通过判断条件进行剪枝：
   • 如果 left 小于 right，说明生成的括号组合是无效的，直接返回。
   • 如果 left 或 right 的数量超过 n，说明已经超出有效范围，直接返回。
4. 如果 left 和 right 都等于 n，则说明已经生成了有效的括号组合，将当前 track 中的括号组合转为字符串并加入 res 数组。
5. 在回溯函数中，分别尝试添加左括号和右括号，并递归调用下一层。之后需要撤销当前的选择，继续尝试下一个选择。
6. 调用回溯函数 backtrack 的初始状态是 (0, 0)，表示左右括号的数量都为 0。
7. 最终返回结果数组 res。

代码

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
	let res = [];
	let track = [];

	const backtrack = (left, right) => {
		if (left < right || left > n || right > n) return;
		if (left == n && right == n) {
			res.push(track.join(''));
			return;
		}
		track.push('(');
		backtrack(left + 1, right);
		track.pop();

		track.push(')');
		backtrack(left, right + 1);
		track.pop();
	};

	backtrack(0, 0);
	return res;
};

相关题目

相关题目

• 17. 电话号码的字母组合
• 20. 有效的括号
• 2116. 判断一个括号字符串是否有效

- [17. 电话号码的字母组合](https://leetcode.com/problems/letter-combinations-of-a-phone-number)
- [20. 有效的括号](./0020.md)
- [2116. 判断一个括号字符串是否有效](https://leetcode.com/problems/check-if-a-parentheses-string-can-be-valid)