22. 括號生成 - 力扣LeetCode數(shù)字n代表生成括號的對數(shù)請你設計一個函數(shù)用于能夠生成所有可能的并且有效的括號組合。示例 1輸入n 3輸出[((())),(()()),(())(),()(()),()()()]示例 2輸入n 1輸出[()]提示1 n 8本質(zhì)在 0, 1, 2, ... , 2n - 1 中選擇 n 個位置填入左括號其余 n 個位置填入右括號。需要注意的是對于這個字符串的任意前綴右括號的個數(shù)必須不大于左括號的個數(shù)因為左括號多了后面還可以補右括號前面的右括號多了后面補左括號也無法構(gòu)成一對括號所以對于單個位置來說問題就變成 選或不選 即選左括號還是選右括號。如果當前左右括號數(shù)量相等那么就必須填左括號如果右括號個數(shù)小于左括號個數(shù)那么填右括號。由于一開始左右括號數(shù)量均為 0按照這個策略第一個位置填入的必然是左括號顯然后續(xù)不可能出現(xiàn)右括號數(shù)量比左括號多的情況這是合理的class Solution: def generateParenthesis(self, n: int) - List[str]: ans [] path [] * (n * 2) # n 個左括號n個右括號 # left:左括號數(shù)量right:右括號數(shù)量 def dfs(left: int, right:int) - None: if right n: # 2n 個括號全部填完 ans.append(.join(path)) return if left n: # 左括號數(shù)量沒有達到 n可以填 path[left right] ( dfs(left 1, right) if right left: path[left right] ) dfs(left, right 1) dfs(0, 0) return ans這里不需要做恢復現(xiàn)場因為是直接覆蓋 left right 位置的元素的pythonfrom typing import List def generateParenthesis(n: int) - List[str]: ans [] path [] * (n * 2) # left: 左括號數(shù)量right: 右括號數(shù)量 def dfs(left: int, right: int) - None: if right n: # 填充完畢 ans.append(.join(path)) return if left n: # 可以填充左括號 path[left right] ( # 直接覆蓋因此如果填充完畢path 不需要清空 dfs(left 1, right) if right left: # 可以填充右括號 path[left right] ) dfs(left, right 1) dfs(0, 0) return ans def main(): with open(input.txt, r) as f: nums f.read().split() # 遍歷 input.txt 中的 n for num in nums: n int(num) result generateParenthesis(n) # 輸出結(jié)果 print(fn {n}) print(result) print() if __name__ __main__: main()Javaimport java.io.BufferedReader; import java.io.FileReader; import java.util.ArrayList; import java.util.List; public class main { static int n; static ListString ans; static char[] path; public static ListString generateParenthesis(int n) { main.n n; ans new ArrayList(); path new char[n * 2]; dfs(0, 0); return ans; } public static void dfs(int left, int right) { if(right n) { // 填充完畢 ans.add(new String(path)); return; } if(left n) { path[left right] (; dfs(left 1, right); } if(right left) { path[left right] ); dfs(left, right 1); } } public static void main(String[] args) throws Exception { BufferedReader br new BufferedReader(new FileReader(input.txt)); StringBuilder sb new StringBuilder(); String line; while((line br.readLine()) ! null) { if(line.isEmpty()) { continue; } int n Integer.parseInt(line.trim()); ListString result generateParenthesis(n); sb.append(n ).append(n).append(\n); sb.append(result).append(\n\n); } System.out.println(sb); } }Gopackage main import ( fmt os strconv strings ) var ans []string var path []byte func dfs(n int, left int, right int) { if right n { ans append(ans, string(path)) return } if left n { path[leftright] ( dfs(n, left1, right) } if right left { path[leftright] ) dfs(n, left, right1) } } func generateParenthesis(n int) []string { ans nil path make([]byte, n*2) dfs(n, 0, 0) return ans } func main() { data, _ : os.ReadFile(input.txt) nums : strings.Fields(string(data)) for _, s : range nums { n, _ : strconv.Atoi(s) result : generateParenthesis(n) fmt.Printf(n %d\n, n) fmt.Println(result) fmt.Println() } }C#includeiostream #includevector #includestring #includefstream using namespace std; vectorstringans; string path; void dfs(int n, int left, int right) { if(right n) { ans.emplace_back(path); return; } if(left n) { path[left right] (; dfs(n, left 1, right); } if(right left) { path[left right] ); dfs(n, left, right 1); } } vectorstring generateParenthesis(int n) { ans.clear(); path string(n * 2, ); dfs(n, 0, 0); return ans; } int main() { ifstream ifs(input.txt); int n; while(ifs n) { auto result generateParenthesis(n); cout n n endl; cout [; for(int i 0; i result.size(); i) { cout result[i]; if(i ! result.size() - 1) { cout ,; } } cout ] endl endl; } return 0; }TypeScriptimport * as fs from fs; function generateParenthesis(n: number) :string[] { let ans:string[] []; let path:string[] new Array(n * 2); function dfs(left: number, right: number) { if(right n) { ans.push(path.join()); return; } if(left n) { path[left right] (; dfs(left 1, right); } if(right left) { path[left right] ); dfs(left, right 1); } } dfs(0, 0); return ans; } function main() { const data fs.readFileSync( input.txt, utf-8 ); const nums data.trim().split(/\s/); for(const s of nums) { const n Number(s); const result generateParenthesis(n); console.log(n ${n}); console.log(result); console.log(); } } main();