阿里，百度，字节跳动面试同时考了它，你需要的题解来了

递归作为基础中的基础，可以说99.99999%的算法面试中会考到，如果因为递归问题挂掉面试，那就真真真真真的太可惜了。

既然递归面试命中率这么高，那努力刷题就万事大吉？
NO！

递归虽然基础，但对初学者极度不友好，算法界流传着这样一句话：

To iterate is human, to recurse, divine.
人理解迭代，神理解递归。

今天我们来一起看一道Google, Uber，Zenefits都考过的真题吧~

【LintCode 427：生成括号】
描述

给定 n，表示有 n 对括号, 请写一个函数以将其生成所有的括号组合，并返回组合结果。

样例

样例 1：
输入: 3
输出: ["((()))", “(()())”, “(())()”, “()(())”, “()()()”]
复制代码

样例 2：
输入: 2
输出: ["()()", “(())”]

参考答案
回溯. 逐个字符添加, 生成每一种组合.
一个状态需要记录的有: 当前字符串本身, 左括号数量, 右括号数量。递归过程中解决:

如果当前右括号数量等于括号对数 n, 那么当前字符串即是一种组合, 放入解中.
如果当前左括号数量等于括号对数 n, 那么当前字符串后续填充满右括号, 即是一种组合.
如果当前左括号数量未超过 n:
如果左括号多于右括号, 那么此时可以添加一个左括号或右括号, 递归进入下一层
如果左括号不多于右括号, 那么此时只能添加一个左括号, 递归进入下一层

此为Python解法，Java，C++解法请见Lintcode
想要更好地掌握这个知识点，欢迎报名免费试听《[递归四讲](https://www.jiuzhang.com/course/52/?utm_source=sc-csdn
-fks)》~

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/JiuZhang_ninechapter/article/details/104045581
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-02-02 19:37:41
阅读 ( 1199 )
分类：面试题

阿里，百度，字节跳动面试同时考了它，你需要的题解来了

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看