22. 括号生成

回溯

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

    /**
     * dfs搜索符合条件的字符串，并加入到res
     * @param res  result列表
     * @param l    剩余左边括号的个数
     * @param r    剩余右边括号的个数
     * @param path 记录当前字符串
     */
    private void dfs(List<String> res, int l, int r, StringBuilder path) {
        // 左右括号都不剩余，递归终止
        if (l == 0 && r == 0) {
            res.add(path.toString());
            return;
        }
        // 如果左括号还剩余的话，可以拼接左括号
        if (l > 0) {
            path.append("(");
            dfs(res, l - 1, r, path);
            path.deleteCharAt(path.length() - 1);
        }
        // 如果右括号剩余左括号剩余的话，可以拼接右括号
        if (r > l) {
            path.append(")");
            dfs(res, l, r - 1, path);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

• 时间复杂度 O(4^n / √n)
• 空间复杂度 O(n)