LC 22
Generate Parentheses
Medium · LC 1–100
候选解法路线
Primary
Free括号匹配栈
Invariant: 扫描前缀后，栈按出现顺序保存且仅保存尚未匹配的开放符；栈顶是唯一允许被下一个关闭符匹配的开放符。
candidate confidence: 0.562 · metadata_only
Alternate 1
Free约束满足回溯
Invariant: 进入递归时 partial assignment 满足所有已激活约束，辅助集合/计数与赋值完全同步；被剪分支不可能扩展为合法完整解。
candidate confidence: 0.610 · metadata_only
Alternate 2
Free子集 / 组合回溯
Invariant: 进入 dfs(start) 时，path 中索引严格递增且来自 [0,start) 的既定选择；此调用只生成以该 path 为前缀、下一索引不小于 start 的答案，因此无重复。
candidate confidence: 0.470 · metadata_only
Alternate 3
Free线性 DP / 一维状态递推
Invariant: 计算完 i 后，所有不超过 i 的状态都等于其定义下的真实最优值/计数；任何未来转移只读取这些已完成状态。
candidate confidence: 0.470 · metadata_only
如何使用本页
先读原题与 constraints，再逐一验证 Recognition signals、invariant 与 complexity；candidate score 不能证明正确性。