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

dfs + 剪枝

为什么要费劲的设置两个参数leftSizes和rightSizes在我的递归函数里头？

• 剪枝呗
• 如果你不这样，每个位置都可以选择左括号或者右括号，到最后再来检查它合不合法。很耗时间
• 加了这两个参数，我们在中间就可以给它提前剪枝了。就很快 ```java public List generateParenthesis(int n) { List list = new ArrayList<>(); char[] path = new char[n << 1]; dfs(0, n, n, path, list); return list; }

public void dfs(int idx, int leftSizes, int rightSizes, char[] path, List list) { if (idx == path.length) { list.add(String.valueOf(path)); return; } //枚举这一层可能的所有选择，选择一种可能之后，进入下一层搜索 // 选择’(‘ if (leftSizes > 0 ) { path[idx] = ‘(‘; dfs(idx + 1, leftSizes - 1, rightSizes, path, list); } // 当（和）数量一样时，只能选择（ if (rightSizes > 0 && rightSizes != leftSizes) { path[idx] = ‘)’; dfs(idx + 1, leftSizes, rightSizes - 1, path, list); } }

- **如果不剪枝就是这样的**
```java
public List<String> generateParenthesis(int n) {
    List<String> list = new ArrayList<>();
    char[] path = new char[n << 1];
    dfs1(0,  path, list);
    return list;
}
public void dfs1(int idx, char[] path, List<String> list) {
    if (idx == path.length) {
        if (isValid(path)) {
            list.add(String.valueOf(path));
            return;
        }
        return;
    }
    path[idx] = '(';
    dfs1(idx + 1,  path, list);
    path[idx] = ')';
    dfs1(idx + 1,  path, list);
}
private boolean isValid(char[] path) {
    int count = 0;
    for (char c : path) {
        if (c == '(') {
            count++;
        } else {
            count--;
        }
        if (count < 0) {
            return false;
        }
    }
    return count == 0;
}

这道题如果要求返回的是合法括号数量有多少个，而不要求求出具体的，那么这道题就是卡特兰数