面试算法85:生成匹配的括号
2024-01-02 19:36:23
题目
输入一个正整数n,请输出所有包含n个左括号和n个右括号的组合,要求每个组合的左括号和右括号匹配。例如,当n等于2时,有两个符合条件的括号组合,分别是"(())“和”()()"。
分析
如果输入n,那么生成的括号组合包含n个左括号和n个右括号。因此生成这样的组合需要2n步,每一步生成一个括号。每一步都面临两个选项,既可能生成左括号也可能生成右括号。由此来看,这个问题很适合采用回溯法解决。
在生成括号组合时需要注意每一步都要满足限制条件。第1个限制条件是左括号或右括号的数目不能超过n个。第2个限制条件是括号的匹配原则,即在任意步骤中已经生成的右括号的数目不能超过左括号的数目。例如,如果在已经生成"()“之后再生成第3个括号,此时第3个括号只能是左括号不能是右括号。如果第3个是右括号,那么组合变成”())",由于右括号的数目超过左括号的数目,之后不管怎么生成后面的括号,这个组合的左括号和右括号都不能匹配。
解
public class Test {
public static void main(String[] args) {
int[] nums = {2, 2, 2, 4, 3, 3};
List<List<Integer>> result = combinationSum2(nums, 8);
for (List<Integer> item : result) {
System.out.println(item);
}
}
public static List<String> generateParenthesis(int n) {
List<String> result = new LinkedList<>();
helper(n, n, "", result);
return result;
}
private static void helper(int left, int right, String parenthesis, List<String> result) {
if (left == 0 && right == 0) {
result.add(parenthesis);
return;
}
if (left > 0) {
helper(left - 1, right, parenthesis + "(", result);
}
if (left < right) {
helper(left, right - 1, parenthesis + ")", result);
}
}
}
文章来源:https://blog.csdn.net/GoGleTech/article/details/135347304
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!