递归作为基础中的基础，可以说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
想要更好地掌握这个知识点，欢迎报名免费试听《递归四讲》
