题解 | #牛圈围栏问题#
牛圈围栏问题
https://www.nowcoder.com/practice/4e3bb97bbc2b4382a745abe953f44aee
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @return string字符串一维数组 */ public String[] generateParenthesis (int n) { // write code here // 用于存储最终结果的列表 List<String> result = new ArrayList<>(); // 回溯生成括号组合 backtrack(result, new StringBuilder(), 0, 0, n); return result.toArray(new String[0]); } private void backtrack(List<String> result, StringBuilder sb, int open, int close, int n) { if (sb.length() == 2 * n) { // 生成了一个完整的括号组合 result.add(sb.toString()); return; } if (open < n) { // 可以添加左括号 sb.append("("); backtrack(result, sb, open + 1, close, n); sb.deleteCharAt(sb.length() - 1); // 回溯,删除最后一个字符 } if (close < open) { // 可以添加右括号 sb.append(")"); backtrack(result, sb, open, close + 1, n); sb.deleteCharAt(sb.length() - 1); // 回溯,删除最后一个字符 } } }
知识点:
递归、回溯
解题分析:
使用回溯算法生成所有可能的括号组合。在每个位置上,可以选择添加左括号或右括号。通过递归调用回溯函数,在选择添加左括号和右括号的过程中,不断向结果列表中添加新的完整括号组合。需要注意的是,添加左括号的数量不能超过n,添加右括号的数量不能超过左括号的数量。
编程语言:
java