SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The task is to generate all combinations of well-formed parentheses given n pairs of parentheses. Each combination should be a string with exactly n pairs of open and close parentheses, arranged in a valid manner.

For example, given n = 3, the valid combinations are:

• ((()))
• (()())
• (())()
• ()(())
• ()()()

Intuition

The problem can be approached using recursive backtracking. We need to ensure that at every step of adding a parenthesis, the resulting string remains valid. This involves keeping track of the number of open and close parentheses used.

The main idea is to use recursion to explore all possible ways of adding parentheses:

1. Start with an empty string and recursively add either an open or a close parenthesis.
2. Maintain counters for the number of open and close parentheses added.
3. Ensure that at any point, the number of close parentheses does not exceed the number of open parentheses.

Approach

1. Initialization: Begin with an empty string and zero counts for both open and close parentheses. Initialize a list to store the results.

2. Recursive Function: Define a recursive function that takes the current state of the string, the counts of open and close parentheses, and the maximum number of pairs.

   • Base Case: If the length of the current string equals twice the maximum number of pairs (2 * n), add it to the results.
   • Add Open Parenthesis: If the count of open parentheses is less than n, recursively add an open parenthesis and continue.
   • Add Close Parenthesis: If the count of close parentheses is less than the count of open parentheses, recursively add a close parenthesis and continue.

3. Return Results: After the recursive function completes, return the list of valid combinations.

Complexity

Time Complexity:

O(4^n / sqrt(n))

The time complexity is derived from the fact that the number of valid combinations grows exponentially with n. The Catalan number C(n) describes the number of valid combinations and can be approximated by 4^n / sqrt(n).

Space Complexity:

O(4^n / sqrt(n))

Space complexity includes the space required for storing the result and the depth of the recursion stack. Since each valid combination is stored and there can be up to 4^n / sqrt(n) valid combinations, the space complexity reflects this growth.

Code

C++

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        generate(result, "", 0, 0, n);
        return result;
    }
private:
    void generate(vector<string>& result, string current, int open, int close, int max) {
        if (current.length() == max * 2) {
            result.push_back(current);
            return;
        }

        if (open < max) {
            generate(result, current + "(", open + 1, close, max);
        }
        if (close < open) {
            generate(result, current + ")", open, close + 1, max);
        }
    }
};

Python

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []
        self._generate(result, "", 0, 0, n)
        return result

    def _generate(self, result: List[str], current: str, open_count: int, close_count: int, max: int):
        if len(current) == max * 2:
            result.append(current)
            return
        
        if open_count < max:
            self._generate(result, current + "(", open_count + 1, close_count, max)
        
        if close_count < open_count:
            self._generate(result, current + ")", open_count, close_count + 1, max)

Java

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        generate(result, "", 0, 0, n);
        return result;
    }
    private void generate(List<String> result, String current, int open, int close, int max) {
        if (current.length() == max * 2) {
            result.add(current);
            return;
        }

        if (open < max) {
            generate(result, current + "(", open + 1, close, max);
        }
        if (close < open) {
            generate(result, current + ")", open, close + 1, max);
        }
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 3;
        List<String> result = solution.generateParenthesis(n);
        for (String s : result) {
            System.out.println(s);
        }
    }
}

JavaScript

var generateParenthesis = function (n) {
    function generate(x) {
        var choice = ["(", ")"];
        if (x === 1) {
            return choice;
        } else {
            var temp = generate(x - 1);
            var res = [];
            for (let i = 0; i < choice.length; i++) {
                for (let j = 0; j < temp.length; j++) {
                    res.push(choice[i] + temp[j]);
                }
            }
            return res;
        }
    }
    var tempRes = generate(2 * n);
    var result = [];
    for (let i = 0; i < tempRes.length; i++) {
        var mark = 0;
        for (let j = 0; j < tempRes[i].length; j++) {
            if (tempRes[i][j] === "(") {
                mark++;
            } else {
                if (mark) mark--;
                else {
                    mark--;
                    break;
                }
            }
        }
        if (mark === 0) result.push(tempRes[i]);
    }
    return result;
};