java实现leetcode 22 括号的生成

Java实现Leetcode 22 - 括号的生成

本文将介绍如何使用Java实现Leetcode 22题 - 括号的生成，并提供相应的代码示例。括号的生成是一个经典的递归问题，通过理解递归的思想和括号生成的规律，我们可以很容易地解决这个问题。

题目描述

给定一个整数n，表示生成括号的对数，编写一个函数来生成所有可能的并且有效的括号组合。

例如，当n=3时，函数应该返回如下结果:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

解题思路

括号的生成涉及到两个变量：左括号的数量和右括号的数量。我们的目标是生成所有可能的组合，并且保证生成的括号组合是有效的。

有效的括号组合满足以下条件：

• 左括号和右括号的数量相等
• 在任意位置，左括号的数量要大于或等于右括号的数量

通过递归的方式，我们可以按照以下步骤生成括号组合：

1. 当左括号的数量小于n时，递归生成左括号并增加左括号的数量
2. 当右括号的数量小于左括号的数量时，递归生成右括号并增加右括号的数量
3. 当左括号和右括号的数量都等于n时，生成一个有效的括号组合

代码示例

以下是Java实现的代码示例：

import java.util.*;

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        generate(result, "", 0, 0, n);
        return result;
    }

    private void generate(List<String> result, String current, int left, int right, int n) {
        // 递归终止条件
        if (left == n && right == n) {
            result.add(current);
            return;
        }

        // 递归生成左括号
        if (left < n) {
            generate(result, current + "(", left + 1, right, n);
        }

        // 递归生成右括号
        if (right < left) {
            generate(result, current + ")", left, right + 1, n);
        }
    }
}

代码解析

• generateParenthesis 方法是入口方法，用于生成括号组合。它调用了 generate 方法来递归生成括号。
• generate 方法接受五个参数：结果集 result，当前生成的括号组合 current，左括号的数量 left，右括号的数量 right 和括号的对数 n。
• generate 方法首先判断是否满足递归终止条件，即左括号和右括号的数量都等于 n。若满足条件，则将当前括号组合加入结果集 result。
• 然后，递归生成左括号。在生成左括号时，需要增加左括号的数量。
• 最后，递归生成右括号。在生成右括号时，需要增加右括号的数量。注意，右括号的数量必须小于左括号的数量。

总结

本文介绍了如何使用Java实现Leetcode 22题 - 括号的生成。通过理解递归的思想和括号生成的规律，我们可以轻松解决这个问题。希望本文对你学习和理解递归算法有所帮助。

完整代码可以在 [GitHub]( 上找到。