leetcode第22題”Generate Parenthese”描述如下:
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
看到題第一想法依然是使用遞歸,思路基本是這樣的,在字符串長度增加的過程中,字符串中”{“的數量肯定要始終大於等於”}”的數量。
所以定義left和right兩個變量方便計數,初試為n,當left等於right時,顯然此時隻能添加”{“,當left小於right時,兩者都可以添加。結束條件為left和right都為0,同時由於left始終小於等於right,所以還要額外判斷僅當left為0的情況,這種情況顯然隻能加”}”。
/** * @param {number} n * @return {string[]} */ var add = function(left, right, stack, s) { if (left === 0 && right === 0) { stack.push(s); return; } if (left === right) { add(left - 1, right, stack, s + "("); } else if (left === 0) { add(left, right - 1, stack, s + ")"); } else { add(left - 1, right, stack, s + "("); add(left, right - 1, stack, s + ")"); } }; var generateParenthesis = function(n) { var stack = []; add(n, n, stack, ""); return stack; };