DeepSeek LeetCode 22. 括号生成 Rust实现

LeetCode 22 题「括号生成」的 Rust 实现最推荐回溯法DFS。核心思路是在递归构建字符串的过程中始终保证已放右括号数不超过左括号数。✅ 方案一回溯法DFS—— 最推荐这是最直观、高效的方法。Rust 中需注意 String 的所有权通常用 mut String 传递并在递归后 pop。implSolution{pubfngenerate_parenthesis(n:i32)-VecString{letmutresultVec::new();letmutcurrentString::new();Self::backtrack(nasusize,0,0,mutcurrent,mutresult);result}fnbacktrack(n:usize,open:usize,close:usize,current:mutString,result:mutVecString){ifcurrent.len()2*n{result.push(current.clone());return;}ifopenn{current.push(();Self::backtrack(n,open1,close,current,result);current.pop();}ifcloseopen{current.push());Self::backtrack(n,open,close1,current,result);current.pop();}}} 方案二动态规划DP利用合法括号组合的性质(A)B其中 A 和 B 都是合法组合。此方法无需递归但需要处理 Vec 的所有权。implSolution{pubfngenerate_parenthesis(n:i32)-VecString{letnnasusize;letmutdpvec![vec![String::new()]];// dp[0] []foriin1..n{letmutcurVec::new();forjin0..i{forleftindp[j]{forrightindp[i-1-j]{cur.push(format!(({}){},left,right));}}}dp.push(cur);}dp.remove(n)}} 方案三BFS广度优先搜索从 “(” 开始逐层扩展当左右括号都用完时收集结果。该方法会同时维护多个状态代码稍显复杂。⚡ 性能与总结· 效率回溯法DFS和 DP 都是最优的时间复杂度为第 n 个卡特兰数 O(4^n / n^(3/2))。· 选择回溯法最推荐因为它最直观、最容易在面试中写出且能自然地处理 Rust 的所有权问题。如果对某个方案的细节还有疑问可以随时再问我。