本文主要是介绍generate Parentheses----leetcode，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.和valid parentheses不一样，valid那个题，只需要遍历序列，当遇到序列的左括号，则入栈，遇到序列的右括号查看栈顶元素是否为左括号可以和当前右括号匹配，如果可以，则将这个栈顶元素（左括号）删除；当遍历完序列后，如果栈为空，则序列是有效的，否则序列是无效的。
2.这个题开始以为和华为oj上的火车进站一样，求序列符号的全排列，后来run code了一发发现不是，好惨。找到了一篇文章，讲得挺好的，思路清晰。
如下：
http://www.1point3acres.com/bbs/thread-172641-1-1.html
所谓Backtracking都是这样的思路：在当前局面下，你有若干种选择。那么尝试每一种选择。如果已经发现某种选择肯定不行（因为违反了某些限定条件），就返回；如果某种选择试到最后发现是正确解，就将其加入解集
所以你思考递归题时，只要明确三点就行：选择 (Options)，限制 (Restraints)，结束条件 (Termination)。即“ORT原则”（这个是我自己编的）
对于这道题，在任何时刻，你都有两种选择：
1. 加左括号。
2. 加右括号。
同时有以下限制：
1. 如果左括号已经用完了，则不能再加左括号了。
2. 如果已经出现的右括号和左括号一样多，则不能再加右括号了。因为那样的话新加入的右括号一定无法匹配。
结束条件是：
左右括号都已经用完。
结束后的正确性：
左右括号用完以后，一定是正确解。因为1. 左右括号一样多，2. 每个右括号都一定有与之配对的左括号。因此一旦结束就可以加入解集（有时也可能出现结束以后不一定是正确解的情况，这时要多一步判断）。
递归函数传入参数：
限制和结束条件中有“用完”和“一样多”字样，因此你需要知道左右括号的数目。
当然你还需要知道当前局面sublist和解集res。
因此，把上面的思路拼起来就是代码：
代码还挺好看懂的：
public static List<String> generateParenthesis2(int n) {List<String> res = new ArrayList<>();backtrack("", res, n, n);return res;}public static void backtrack(String sublist, List<String> res, int left, int right) {if (left == 0 && right == 0) {res.add(sublist);return;}if (left > right)return;if (left > 0)backtrack(sublist + "(", res, left - 1, right);if (right > 0)backtrack(sublist + ")", res, left, right - 1);}等我吃完饭来自己写一发。~~~~
这篇关于generate Parentheses----leetcode的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
