Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

We can generate all 22n sequences of '(' and ')' characters. Then, we will check if each combination is valid. To generate all sequences, we use recursion. All sequences of length n is just '(' plus all sequences of length n-1, and then ')' plus all sequences of length n-1. To check whether a sequence is valid, we keep track of balance, the net number of opening brackets minus closing brackets. If it falls below zero at any time or doesn’t end with zero, the sequence is invalid – otherwise, it is valid.

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        char[] res = new char[2 * n];
        generate(result, 0, res);
        return result;
    }

    private void generate(List<String> result, int pos, char[] res) {
        if (res.length == pos) {
            if (isValidCombination(res)) {
                result.add(String.valueOf(res));
            }
        } else {
            res[pos] = '(';
            generate(result, (pos + 1), res);
            res[pos] = ')';
            generate(result, (pos + 1), res);
        }
    }

    private boolean isValidCombination(char[] res) {
        int balance = 0;
        for (char c : res) {
            if (c == '(') balance++;
            else balance--;
            if (balance < 0) return false;
        }
        return balance == 0;
    }
}

Complexity Analysis:

  • Time Complexity:  O(22n). For each of the 2n sequences, we need to create and validate the sequence, which takes O(n) work.
  • Space Complexity: O(22n). Naively, every sequence could be valid.

Instead of adding '(' or ')' every time as in the above solution let’s only add them when we know it will remain a valid sequence. We can do this by keeping track of the number of opening brackets we have placed so far. As for input, n we can have only n number of opening parentheses in a valid sequence. So discard all the sequences where the number of open parentheses crosses n, as this can never be a valid sequence. In the same contrast discard all sequences where number of closed parentheses is greater the number of open parentheses.

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if (n == 0) {
            return result;
        }
        char[] buffer = new char[2 * n];
        generateParenthesis(buffer, result, 0, 0, 0, n);
        return result;
    }

    private void generateParenthesis(char[] buffer, List<String> result,
                                     int pos, int open, int closed, int max) {
        if (pos == (2 * max)) {
            result.add(String.valueOf(buffer));
        } else {
            if (open < max) {
                buffer[pos] = '(';
                generateParenthesis(buffer, result, pos + 1, open + 1, closed, max);
            }
            if (closed < open) {
                buffer[pos] = ')';
                generateParenthesis(buffer, result, pos + 1, open, closed + 1, max);
            }
        }
    }
}

Complexity Analysis:

We have Catalan(n) valid expressions, and each expression’s length is 2n, the backtracking approach adds at least one character to the expression each time, so the time complexity is O(Catalan(n) * 2n). It’s not tight though, as the valid expressions have common parts, when the function adds one character to the common part of the expressions, it’s equivalent to adding one character to each of the expressions with that comon part. As a result, it’s less than Catalan(n) * 2n. I think O(Catalan(n) * 2n) is okay. After all, big O notation is not a tight upper bound on the growth rate of the function, it’s just an upper bound. And O(4^n/n^0.5) is a more close upper bound.

Catalan(n) = (2n)!/((n+1)!*n!)


Categories: Backtracking

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s