【回溯】Leetcode 22. 括号生成【中等】

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

解题思路

• 1、使用回溯算法来生成所有有效的括号组合。
• 2、对于每个位置，可以选择放置左括号或右括号。
• 3、放置左括号的条件是左括号的数量小于n，放置右括号的条件是右括号的数量小于左括号的数量。
• 4、使用递归回溯的方法，尝试放置每个括号，并继续向下搜索。

java实现

public class GenerateParentheses {public List<String> generateParenthesis(int n) {List<String> result = new ArrayList<>();backtrack(n, 0, 0, "", result);return result;}private void backtrack(int n, int left, int right, String combination, List<String> result) {if (left == n && right == n) {result.add(combination);return;}//左括号的数量小于nif (left < n) {backtrack(n, left + 1, right, combination + "(", result);}//右括号的数量小于左括号的数量if (right < left) {backtrack(n, left, right + 1, combination + ")", result);}}public static void main(String[] args) {GenerateParentheses solution = new GenerateParentheses();int n = 3;List<String> combinations = solution.generateParenthesis(n);System.out.println("All possible combinations of valid parentheses:");for (String combination : combinations) {System.out.println(combination);}}
}

时间空间复杂度

• 时间复杂度：由于回溯算法的性质，最坏情况下时间复杂度为O(2 ^
  2n ⋅n)即 O(4^n / √n)，其中n是括号对数。

• 空间复杂度：O(n)，递归调用栈的深度为括号对数n。