【回溯】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;
        }
        //左括号的数量小于n
        if (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);
        }
    }
}