22 LeetCode Generate Parentheses problem solution

LeetCode problem link: 22. Generate Parentheses


LeetCode 22. Generate Parentheses problem description

Medium level problem.


Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.


Example 1:


Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]


Example 2:


Input: n = 1
Output: ["()"]


Constraints

  • 1 <= n <= 8

LeetCode 22. Generate Parentheses problem solution

I use Backtracking to build each valid combination one character at a time.

Backtracking is a technique where we build a solution step by step, and if the current path cannot lead to a valid result, we stop exploring it and go back.


Keep two counters:

  • open - number of ( already added.
  • close - number of ) already added.

At each step:

  • Add ( if open < n.
  • Add ) only if close < open. This guarantees that a closing parenthesis never appears without a matching opening parenthesis before it.
  • When the current string has length 2 * n, it contains exactly n opening and n closing parentheses, so add it to the result.

Most important tip: this approach generates only valid combinations, so it does not need a separate validation step.


Patterns | Techniques | Data Structures

Backtracking - technique


Complexity

Time Complexity - O(Cn * n)

The number of valid combinations of n pairs of parentheses is the n-th Catalan number. A Catalan number is part of a sequence of numbers that, among other things, represents the number of valid combinations of n pairs of parentheses.

Cn = (1 / (n + 1)) * binomial(2n, n)

For example, n = 3


C3 = (1 / (3 + 1)) * binomial(6, 3), where binomial(6, 3) - this is the number of ways to choose 3 elements from 6:
binomial(6, 3) = 6! / (3! * 3!) = 20
then:
C3 = (1 / 4) * 20 = 5


There are Cn valid strings, and each result contains 2 * n characters. Creating/storing each complete string therefore takes O(n) time.

So the total time complexity is O(Cn * n) because Cn is not a constant, it is a function of n.


Space Complexity - O(n)

The recursion depth is at most 2 * n, and the current combination contains at most 2 * n characters, so the auxiliary space is O(n).

If the returned results are included, the total space is O(Cn * n) because all Cn strings of length 2 * n must be stored.


LeetCode 22. Generate Parentheses problem example

For n = 3, we need strings of length 6 containing three ( and three ).

Start with an empty string:

""

We cannot add ) because close = open = 0, so we add (.

Now open = 1, close = 0. We have two possible choices: add another ( or add ).

Following the first branch:

(
((
(((

At (((, open = 3, so no more opening parentheses can be added. We must close them:

((()
((())
((()))

((())) has length 6, so it is added to the result.

Backtracking returns to earlier states and tries the other valid choices. For example:

((
(()
(()(
(()()
(()())

This produces another valid result: (()()).

Continuing the same process explores all valid branches:

((()))
(()())
(())()
()(())
()()()

The algorithm never creates a prefix such as ()) because ) can only be added when close < open.


LeetCode 22 C++ solution

class Solution {
public:
    vector<string> generateParenthesis(int n) 
    {
        vector<string> result;
        string current;

        backtrack(n, 0, 0, current, result);

        return result;
    }

private:
    void backtrack(int n, int open, int close, string& current, vector<string>& result)
    {
        // A complete valid combination has 2 * n characters.
        if(current.size() == 2 * n)
        {
            result.push_back(current);

            return;
        }

        // Add '(' while we still have opening parentheses available.
        if(open < n) 
        {
            current.push_back('(');
            backtrack(n, open + 1, close, current, result);
            current.pop_back(); // Backtrack.
        }

        // Add ')' only when there is an unmatched '(' before it.
        if(close < open) 
        {
            current.push_back(')');
            backtrack(n, open, close + 1, current, result);
            current.pop_back(); // Backtrack.
        }
    }
};

LeetCode 22 Java solution

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        StringBuilder current = new StringBuilder();

        backtrack(n, 0, 0, current, result);

        return result;
    }

    private void backtrack(int n, int open, int close, StringBuilder current, List<String> result) {
        // A complete valid combination has 2 * n characters.
        if(current.length() == 2 * n) {
            result.add(current.toString());

            return;
        }

        // Add '(' while we still have opening parentheses available.
        if(open < n) {
            current.append('(');
            backtrack(n, open + 1, close, current, result);
            current.deleteCharAt(current.length() - 1); // Backtrack.
        }

        // Add ')' only when there is an unmatched '(' before it.
        if(close < open) {
            current.append(')');
            backtrack(n, open, close + 1, current, result);
            current.deleteCharAt(current.length() - 1); // Backtrack.
        }
    }
}

LeetCode 22 JavaScript solution

var generateParenthesis = function(n) {
    const result = [];

    const backtrack = (current, open, close) => {
        // A complete valid combination has 2 * n characters.
        if(current.length === 2 * n) {
            result.push(current);

            return;
        }

        // Add '(' while we still have opening parentheses available.
        if(open < n) {
            backtrack(current + '(', open + 1, close);
        }

        // Add ')' only when there is an unmatched '(' before it.
        if(close < open) {
            backtrack(current + ')', open, close + 1);
        }
    };

    backtrack('', 0, 0);

    return result;
};

LeetCode 22 TypeScript solution

function generateParenthesis(n: number): string[] {
    const result: string[] = [];

    const backtrack = (current: string, open: number, close: number): void => {
        // A complete valid combination has 2 * n characters.
        if(current.length === 2 * n) {
            result.push(current);

            return;
        }

        // Add '(' while we still have opening parentheses available.
        if(open < n) {
            backtrack(current + '(', open + 1, close);
        }

        // Add ')' only when there is an unmatched '(' before it.
        if(close < open) {
            backtrack(current + ')', open, close + 1);
        }
    };

    backtrack('', 0, 0);

    return result;
}

LeetCode 22 Python solution

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []
        current = []

        def backtrack(open_count: int, close_count: int) -> None:
            # A complete valid combination has 2 * n characters.
            if len(current) == 2 * n:
                result.append("".join(current))

                return

            # Add '(' while we still have opening parentheses available.
            if open_count < n:
                current.append("(")
                backtrack(open_count + 1, close_count)
                current.pop()  # Backtrack.

            # Add ')' only when there is an unmatched '(' before it.
            if close_count < open_count:
                current.append(")")
                backtrack(open_count, close_count + 1)
                current.pop()  # Backtrack.

        backtrack(0, 0)
        
        return result