LEETCODE-括号生成

题目简述

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

示例 1：

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

解题思路

根据减枝+回溯图解可以得出以下结论：

• 当前左右括号都有大于 000 个可以使用的时候，才产生分支；

• 产生左分支的时候，只看当前是否还有左括号可以使用；

• 产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以产生分支；

• 在左边和右边剩余的括号数都等于 000 的时候结算。

package org.xnqx.ptbf;

import java.util.ArrayList;
import java.util.List;

public class LeetCode_22 {

    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }

    public static List<String> generateParenthesis(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }

        ArrayList<String> resultList = new ArrayList<>();
        dfs("",n,n,resultList);
        return resultList;
    }

    public static void dfs(String resultString, int left, int right, List<String> resultList) {

        if (left == 0 && right == 0) {
            resultList.add(resultString);
            return;
        }

        if (left > right) {
            return;
        }

        if (left > 0) {
            dfs(resultString + "(", left - 1, right, resultList);
        }
        if (right > 0) {
            dfs(resultString + ")", left, right - 1, resultList);
        }
    }
}

执行结果