n 对括号的所有合法组合

简介: 前端西瓜哥

大家好,我是前端西瓜哥,今天来看一道回溯题。

求 n 对括号的所有合法组合,要求返回一个字符串数组。比如 n 为 3 时,要求返回:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

代码实现

思路是回溯,题目的特征也比较明显。

我们先看代码实现。

function generateParenthesis(n: number): string[] {
  const arr: string[] = [];
  r(arr, '', n, n);
  return arr;
};
// leftRem: 左括号剩余数
// rightRem: 右括号剩余数
function r(arr: string[], str: string, leftRem: number, rightRem: number) {
  // 左括号使用量超过 n
  // 以及右括号使用数超过左括号,都是不合法的。
  if (leftRem < 0 || rightRem < leftRem) return;
  if (leftRem === 0 && rightRem === 0) {
    arr.push(str);
    return;
  }
  r(arr, str + '(', leftRem - 1, rightRem);
  r(arr, str + ')', leftRem, rightRem - 1);
}

这里简单说说回溯是怎么一个原理。

回溯就好比我们遇到岔路时,选择一条路走完后,我们再可以回到当前这个岔路口,走另一条路。岔路走完后,我们又回到上一个岔路,直到所有的路都走完。

可以看出,回溯本质是穷举。

n 对括号问题同样的道理,我们将会遇到 n 个岔路口,每个岔路口,我们有两个选择,是选择左括号呢还是右括号

r(arr, str + '(', leftRem - 1, rightRem);
r(arr, str + ')', leftRem, rightRem - 1);

但我们有可能会得到不合法的组合,有两种情况:

  1. 左括号使用数量超过 n
  2. 在添加括号的过程中,使用的右括号数不能超过左括号数。如果超过了,就说明至少有一个左括号没对象,这不合法。

还有一种情况是右括号数超过 n,但它可以由上面两种情况的组合推导而出,所以就不做讨论了。

下图为 n = 2 时,回溯的过程,其中橙色叉叉代表情况 1,红色叉叉代表情况 2。

image.png


当这两种情况发生时,就代表此路不通,不需要继续递归下去了,直接 return。

if (leftRem < 0 || rightRem < leftRem) return;

此外我们还需要知道 str 字符串变成一个合法的组合的时机。

可以是 leftRem 和 rightRem 都为 0,可以是 str 长度为 n。但我们偷懒没传 n,所以就用前者吧。

if (leftRem === 0 && rightRem === 0) {
  arr.push(str);
  return;
}

结尾

求 n 对括号的所有合法组合的题目,解法为回溯。每次选择左括号或右括号进入下一个阶段,并更新对应的一些状态(剩余数减一)。

这些状态会在后续的回溯中作为判断合法与否的条件,在特定时机结束递归。

我是前端西瓜哥,欢迎关注我。

相关文章
|
8月前
|
JavaScript 前端开发 Java
|
6月前
|
语音技术 数据安全/隐私保护
语音识别,猜猜心里数字讲解,猜数字的组合,判断语句的嵌套,嵌套语句使用很简单,我们写一个外层嵌套的条件,利用缩进,满足条件,才会执行条件2,判断语句综合案例,如何产生变量的随机数字,while循环应用
语音识别,猜猜心里数字讲解,猜数字的组合,判断语句的嵌套,嵌套语句使用很简单,我们写一个外层嵌套的条件,利用缩进,满足条件,才会执行条件2,判断语句综合案例,如何产生变量的随机数字,while循环应用
|
8月前
判断字符类型
该内容描述了一个字符判断和转换的逻辑:输入字符,根据条件进行操作。如果字符是大写字母,转为小写;如果是小写字母,转为大写;若是数字,输出其ASCII值;否则输出&quot;错误&quot;。判断条件包括:大写字母ASCII值在&#39;A&#39;和&#39;Z&#39;之间,小写字母在&#39;a&#39;和&#39;z&#39;之间,数字在&#39;0&#39;和&#39;9&#39;之间。转换利用ASCII值差32的特性,通过if-else if语句实现。内容中还包括两幅示例图片,显示了程序执行的结果。
56 1
|
8月前
|
Python
什么是语句?什么是表达式?怎么区分?
编程语言中的语句和表达式是基础概念。语句是执行操作或命令的代码行,如Python的`print("Hello, World!")`,通常以换行符结束。表达式则表示值或计算过程,如`2 + 2`,可赋值给变量或用于计算。语句侧重于执行动作,表达式侧重于计算值。表达式可含运算符、变量等,而语句由主语和谓语构成。示例中,`x = 10`和`print("Hello, World!")`是语句,`y = x + 5`和`result = a * b + c`是表达式。
|
8月前
|
C++
HRBUST - 1170(判断括号是否匹配)
HRBUST - 1170(判断括号是否匹配)
蓝桥——括号合法组合 2020-11-26
蓝桥——括号合法组合 2020-11-26
|
算法 前端开发 JavaScript
【前端算法】判断一个字符串的括号是否成对匹配
使用typescript完成判断一个字符串的括号是否成对匹配的过程
137 0
C++学习——c++逗号操作符说明(附加全部运算符优先级)
C++学习——c++逗号操作符说明(附加全部运算符优先级)
213 0
C++学习——c++逗号操作符说明(附加全部运算符优先级)
括号合法性问题(匹配、删除与生成)
括号合法性问题(匹配、删除与生成)
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等