22. Generate Parentheses

五刷 06/2022

Version #1 Backtracking

关于复杂度分析答案里面提到了catalan numbers formula，感觉面试的时候不可能记起来

比较loose的一个分析是作为permutation with repetition

Time O((2N)!/(N!N!))

The number of permutations of $n$ objects with $n_1$ identical objects of type 1, $n_2$ identical objects of type 2, $\ldots$, and $n_k$ identical objects of type $k$ is

$\frac{n!}{n_1! n_2! \cdots n_k!}.$

Space O(2N)

Runtime: 1 ms, faster than 97.37% of Java online submissions for Generate Parentheses.

Memory Usage: 44.2 MB, less than 25.45% of Java online submissions for Generate Parentheses.

class Solution {

    public List<String> generateParenthesis(int n) {

        // If number of right parentheses is equals to the number of left parentheses, then we cannot add more right parentheses

        // We need to guarantee that at any point of our recursion, the count of right parentheses is smaller or equals to the count of left parentheses

        List<String> result = new ArrayList<>();

        helper(0, 0, n, new StringBuilder(), result);

        return result;

    }

    

    private void helper(int leftCount, int rightCount, int n, StringBuilder sb, List<String> result) {

        if (leftCount == n && rightCount == n) {

            result.add(sb.toString());

            return;

        }

        if (leftCount < n) {

            sb.append("(");

            helper(leftCount + 1, rightCount, n, sb, result);

            sb.deleteCharAt(sb.length() - 1);

        }

        if (rightCount < leftCount) {

            sb.append(")");

            helper(leftCount, rightCount + 1, n, sb, result);

            sb.deleteCharAt(sb.length() - 1);

        }

    }

}

四刷

Runtime: 0 ms, faster than 100.00% of Java online submissions for Generate Parentheses.

Memory Usage: 39 MB, less than 74.25% of Java online submissions for Generate Parentheses.

和一刷三刷基本一样，不知道为什么可以beats100%

Time complexity O(2^n)

class Solution {

    public List<String> generateParenthesis(int n) {

        List<String> result = new ArrayList<>();

        dfs(n, 0, 0, result, new StringBuilder());

        return result;

    }

    

    private void dfs(int n, int leftCnt, int rightCnt, List<String> result, StringBuilder sb) {

        if (leftCnt == n && rightCnt == n) {

            result.add(sb.toString());

            return;

        }

        if (leftCnt < n) {

            sb.append("(");

            dfs(n, leftCnt + 1, rightCnt, result, sb);

            sb.deleteCharAt(sb.length() - 1);

        }

        if (rightCnt < leftCnt) {

            sb.append(")");

            dfs(n, leftCnt, rightCnt + 1, result, sb);

            sb.deleteCharAt(sb.length() - 1);

        }

    }

}

三刷
92.68 %
代码和一刷一样哈哈哈哈哈哈


二刷
一刷的代码好奇怪。。。自己都看不太懂了
90.22 %
/*
stop:
    succees:#left == #right == n
    failure:#right > #left || #left > n
for every recursion layer:
    (1)add 1 parenthesis either left or right
    (2)call dfs for the next layer
*/
public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if (n <= 0) return result;
        dfs(n, 0, 0, result, new StringBuilder());
        return result;
    }
 
    private void dfs(int n, int left, int right, List<String> result, StringBuilder path) {
        if (left == n && right == left) {
            result.add(path.toString());
            return;
        }
        //need: left <= n && right <= right
        if (right > left || left > n) return;
        //Choose to add left parenthesis
        path.append("(");
        dfs(n, left + 1, right, result, path);
        path.deleteCharAt(path.length() - 1);
        //add right parenthesis
        path.append(")");
        dfs(n, left, right + 1, result, path);
        path.deleteCharAt(path.length() - 1);
    }
 
}

一刷
60.62% 
public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if (n <= 0) return result;
        helper(n, 0, 0, result, new StringBuilder());
        return result;
    }
 
    public void helper(int n, int left, int right, List<String> result, StringBuilder path) {
        if (left == n && right == n) {
            result.add(path.toString());
            return;
        }
        if (left < n) {
            path.append('(');
            helper(n, left + 1, right, result, path);
            path.deleteCharAt(path.length() - 1);
        }
        if (right < left) {
            path.append(')');
            helper(n, left, right + 1, result, path);
            path.deleteCharAt(path.length() - 1);
        }
    }
}