备考首页> 数据结构> 字符串
61

编程题 61 /86

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。
例如，给出n=3，解集为：
"((()))", "(()())", "(())()", "()()()", "()(())"

数据范围：
要求：空间复杂度 O(n)，时间复杂度 O(2^n)

参考答案

dfs+剪枝。对于每个位置要么是左括号要么是右括号，对应dfs的两个递归情况，遇到不合法的可以提前剪枝掉。
纠错 收藏
查看讨论
上一题 下一题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号