力扣(LeetCode)22

题目地址：

https://leetcode-cn.com/probl...

题目描述：

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[

"((()))",

"(()())",

"(())()",

"()(())",

"()()()"

]

解答：

这一题可以用递归来做，若现在有n-1对的有效括号组合，求第n对的有序括号组合，只需要在n-1对的组成中不断添加"()"就可以保证生成有效的括号组合，不过这样可能会重复，因此再使用一个hash表来去重。

java ac代码:

class Solution {
    HashSet<String> set = new HashSet(2000);
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        if(n == 1)
        {
            ans.add("()");
            set.add("()");
            return ans;
        }
        List<String>temp = 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;
        
    }
}

不过这一题标准的解法是回溯法。回溯法在生成全集的过程中进行剪枝，使得效率最大。并且不需要判重，因为回溯就是一次性生成全集，所以不会重复。剪枝需要用到两个变量，一个是当前过程中左括号数量l和当前过程中右括号数量r，若r>l则一定无解，则剪去这个部分。

java ac代码：

class Solution {
    List<String> ans = new ArrayList();
    public List<String> 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);
        
    }
}