力扣22-括号生成

22. 括号生成 - 力扣LeetCode数字n代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且有效的括号组合。示例 1输入n 3输出[((())),(()()),(())(),()(()),()()()]示例 2输入n 1输出[()]提示1 n 8本质在 0, 1, 2, ... , 2n - 1 中选择 n 个位置填入左括号其余 n 个位置填入右括号。需要注意的是对于这个字符串的任意前缀右括号的个数必须不大于左括号的个数因为左括号多了后面还可以补右括号前面的右括号多了后面补左括号也无法构成一对括号所以对于单个位置来说问题就变成 选或不选 即选左括号还是选右括号。如果当前左右括号数量相等那么就必须填左括号如果右括号个数小于左括号个数那么填右括号。由于一开始左右括号数量均为 0按照这个策略第一个位置填入的必然是左括号显然后续不可能出现右括号数量比左括号多的情况这是合理的class Solution: def generateParenthesis(self, n: int) - List[str]: ans [] path [] * (n * 2) # n 个左括号n个右括号 # left:左括号数量right:右括号数量 def dfs(left: int, right:int) - None: if right n: # 2n 个括号全部填完 ans.append(.join(path)) return if left n: # 左括号数量没有达到 n可以填 path[left right] ( dfs(left 1, right) if right left: path[left right] ) dfs(left, right 1) dfs(0, 0) return ans这里不需要做恢复现场因为是直接覆盖 left right 位置的元素的pythonfrom typing import List def generateParenthesis(n: int) - List[str]: ans [] path [] * (n * 2) # left: 左括号数量right: 右括号数量 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) # 输出结果 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();