LeetCode-Generate Parentheses

https://leetcode-cn.com/problems/generate-parentheses/submissions/

使用递归+双层循环的方式来解决。主要思路是将当前状态中所有可以成对的可能性都考虑到，先考虑左括号，再考虑右括号。然后让每种可能性都递归下去。

代码还有 bug（因为结果会产生许多长度不满足的数组），不过已经可以 Accept 了，而且只击败了 24% 的人。

class Solution {
    public List<String> ret;
    public void gp(int n, int l, int r, String nowStr){
        if(l==n && r==n){
            if(nowStr.length()==n*2) ret.add(nowStr);
        }
        String ts1=nowStr;
        while(l<n){
            l++;
            String ts2=ts1+"(";
            gp(n,l,r,ts2);
            while(r<l){
                r++;
                ts2=ts2+")";
                gp(n,l,r,ts2);
            }
        }
    }
    public List<String> generateParenthesis(int n) {
        ret=new ArrayList<>();
        gp(n,0,0,"");
        return ret;
    }
}

经过检查，是因为 Java 的字符串赋值是传递地址的，必须使用传递值才可以。所以有了如下的方案，但是因为会出现重复结果，所以使用了 HashSet 转 ArrayList。

class Solution {
    public Set<String> res;
    public void gp(int n, int l, int r, String nowStr){
        if(l==n && r==n) res.add(nowStr);
        while(l++<n){
            nowStr+="(";
            gp(n,l,r,nowStr);
            String ts=new String(nowStr);
            int tr=r;
            while(tr++<l){
                ts=ts+")";
                gp(n,l,tr,ts);
            }
        }
    }
    public List<String> generateParenthesis(int n) {
        res=new HashSet<>();
        gp(n,0,0,"");
        return new ArrayList<String>(res);
    }
}

但发现速度更慢了，只击败了 4%的人。原因应该是数组的重复复制以及 hashset 去重。

看了一下 Solutions 中的答案，发现方法二 Backtracking（回溯算法）和我之前的很像，不过我在一次递归中考虑的太多，导致重复。

所以，在回溯里只要考虑下一步做什么就可以了，不要考虑这么多。

class Solution {
    public List<String> res;
    public void gp(int n, int l, int r, String nowStr){
        if(nowStr.length()==n*2){
            res.add(nowStr);
            return;
        }
        if(l<n){
            gp(n,l+1,r,nowStr+"(");
        }
        if(r<l){
            gp(n,l,r+1,nowStr+")");
        }
    }
    public List<String> generateParenthesis(int n) {
        res=new ArrayList<>();
        gp(n,0,0,"");
        return res;
    }
}

最后， solution 给出了一个最简单的方法。可以构成成堆的括号的标准就是有一个东西把另外的东西括起来，所以以括号为单位进行递归是最方便的选择。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        if (n == 0) {
            ans.add("");
        } else {
            for (int c = 0; c < n; ++c)
                for (String left: generateParenthesis(c))
                    for (String right: generateParenthesis(n-1-c))
                        ans.add("(" + left + ")" + right);
        }
        return ans;
    }
}

时间过去了快一年，这里是我现在的解法，同样是回溯法，但简洁了许多。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        if(n<=0) return result;
        generate(result, "", n, 0);
        return result;
    }
    void generate(vector<string>& result, string now, int nleft, int unpaired) {
        if(nleft==0 && unpaired==0) {
            result.push_back(now);
            return;
        }
        if(nleft!=0) generate(result, now+'(', nleft-1, unpaired+1);
        if(unpaired!=0) generate(result, now+')', nleft, unpaired-1);
    }
};