Generate Parentheses (M)
題目
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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
題意
指定整數n，要求輸出n個括號對的所有合理組合排序(即所有左括號都有對應的右括號)，
思路
排列組合問題很容易想到回溯法：每次遞回時，記錄待插入的右括號的個數count，以及已經插入的左括號的個數n，當n為0時，說明已經插入所有左括號，只要按count補齊右括號即可添加到答案串列中，分兩種情況遞回：一是只添加左括號，二是當右括號剩余數有盈余時只添加右括號，
代碼實作
Java
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
generate("", 0, n, ans);
return ans;
}
// count記錄待添加的右括號數，n記錄已插入的左括號數
private void generate(String s, int count, int n, List<String> ans) {
if (n == 0) {
for (int i = 0; i < count; i++) {
s += ")";
}
ans.add(s);
return;
}
// 只添加左括號進行遞回
generate(s + "(", count + 1, n - 1, ans);
// 有多余右括號待添加時，只添加右括號進行遞回
if (count > 0) {
generate(s + ")", count - 1, n, ans);
}
}
}
JavaScript
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function (n) {
let list = []
dfs('', list, n, 0)
return list
}
let dfs = function (s, list, left, right) {
if (left === 0) {
while (right !== 0) {
s += ')'
right--
}
list.push(s)
}
dfs(s + '(', list, left--, right)
if (right > 0) {
dfs(s + ')', list, left, right--)
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/41145.html
標籤：其他
上一篇：POJ 1000：兩數之和