力扣(LeetCode)22

dack 發(fā)布于2019-08-16 15:16 / 3496人閱讀

摘要：代碼不過這一題標(biāo)準(zhǔn)的解法是回溯法。回溯法在生成全集的過程中進(jìn)行剪枝，使得效率最大。并且不需要判重，因?yàn)榛厮菥褪且淮涡陨扇圆粫貜?fù)。

題目地址：
https://leetcode-cn.com/probl...
題目描述：
給出 n 代表生成括號的對數(shù)，請你寫出一個(gè)函數(shù)，使其能夠生成所有可能的并且有效的括號組合。

例如，給出 n = 3，生成結(jié)果為：

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
解答：
這一題可以用遞歸來做，若現(xiàn)在有n-1對的有效括號組合，求第n對的有序括號組合，只需要在n-1對的組成中不斷添加"()"就可以保證生成有效的括號組合，不過這樣可能會重復(fù)，因此再使用一個(gè)hash表來去重。
java ac代碼:

class Solution {
    HashSet set = new HashSet(2000);
    public List generateParenthesis(int n) {
        List ans = new ArrayList();
        if(n == 1)
        {
            ans.add("()");
            set.add("()");
            return ans;
        }
        Listtemp = generateParenthesis(n-1);
        for(String s:temp)
        {
            int k = 0;
            while(k < s.length()){
            if(!set.contains(s.substring(0,k+1)+"()"+s.substring(k+1))){
            ans.add(s.substring(0,k+1)+"()"+s.substring(k+1));
            set.add(s.substring(0,k+1)+"()"+s.substring(k+1));
            
            }
            k++;   
            }
            
            
        }
        return ans;
        
    }
}

不過這一題標(biāo)準(zhǔn)的解法是回溯法。回溯法在生成全集的過程中進(jìn)行剪枝，使得效率最大。并且不需要判重，因?yàn)榛厮菥褪且淮涡陨扇圆粫貜?fù)。剪枝需要用到兩個(gè)變量，一個(gè)是當(dāng)前過程中左括號數(shù)量l和當(dāng)前過程中右括號數(shù)量r，若r>l則一定無解，則剪去這個(gè)部分。
java ac代碼：

class Solution {
    List ans = new ArrayList();
    public List generateParenthesis(int n) {
       
        char[]temp = new char[n*2];
        temp[0] = "(";
        backtrack(1,n*2,1,0,temp);
        return ans;
        
    }
    
    void backtrack(int i,int n,int l,int r,char[]temp)
    {
        if(i == n)
        {
            if(l == r)
            ans.add(new String(temp));
            return;
        }
        if(r>l)return;

        temp[i] = "(";
        backtrack(i+1,n,l+1,r,temp);
        temp[i] = ")";
        backtrack(i+1,n,l,r+1,temp);
        
    }
}