LeetCode——括号生成

NO.22 括号生成中等

思路一：暴力法 1. 将2*n个括号的序列全部得到。2. 同时判断其是否为有效序列。如果是则加入结果集。

	List<String> res=new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs(0,"",n);
        return res;
    }

//    深度优先遍历得到所有组合序列，如果是有效序列，则加入结果集
    public void dfs(int index,String conbination,int n){
        if (index==2*n){
            if (isValid(conbination))res.add(conbination);
            return;
        }else {
            dfs(index+1,conbination+'(',n);
            dfs(index+1,conbination+')',n);
        }
    }

//    平衡法判断括号序列是否有效
    public boolean isValid(String s){
        int balance=0;
        for (int i=0;i<s.length();i++){
            if (s.charAt(i)=='('){
                balance++;
            }else {
                balance--;
            }
//            如果balance<0则说明，)出现在与其对应的(之前，或者)多于(
            if (balance<0)return false;
        }
        return balance==0;
    }

时间复杂度：O(2^2n*n)

思路二：回溯法 该方法是对上面的暴力法的一个优化思路。上面的方法需要组合出所有的序列(有效的和无效的)，思路就是不生成无效的序列(或者说是”剪枝”,剪除无效无效序列)。观察有效序列的特点：1. 因为是括号’对’，所以n对括号序列中的’(‘和’)’的数量都是n个。2. ‘)’不能出现在与其成对的’(‘之前。

针对上述细节，思考回溯算法细节：

当’(‘和’)’的数量都是n个的时候，说明已经得到括号序列。
‘(‘数量小于n的时候，可以向序列中继续添加’(‘。
‘)’数量小于n并且当前’)’数量小于当前’(‘数量时，才可以向序列中继续添加’)’。

	List<String> res=new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        dfs(0,0,"",n);
        return res;
    }

    /**
     * @param l 左括号数量
     * @param r 有括号数量
     * @param combination 当前括号序列
     * @param n 输入n
     */
    public void dfs(int l,int r,String combination,int n){
//        当'('和')'的数量都是n个的时候，说明已经得到括号序列。
        if (l==n&&r==n){
            res.add(combination);
            return;
        }
//        '('数量小于n的时候，可以向序列中继续添加'('。
        if (l<n){
            dfs(l+1,r,combination+'(',n);
        }
//        ')'数量小于n并且当前')'数量小于当前'('数量时，才可以向序列中继续添加')'。
        if (r<n&&r<l){
            dfs(l,r+1,combination+')',n);
        }
    }

时间复杂度：O(4^n/sqrt(n))。在回溯过程中，每个有效序列最多需要n步。

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github

NO.22 括号生成 中等

NO.22 括号生成中等