DevExCode

22. Generate Parentheses

StringDynamic ProgrammingBacktracking

Explanation

To generate all combinations of well-formed parentheses, we can use a backtracking approach. At each step, we have two choices: either add an open parenthesis '(', or add a close parenthesis ')'. We need to ensure that the parentheses are well-formed by keeping track of the number of open and close parentheses used.

We can start with an empty string and add parentheses recursively while keeping track of the number of open and close parentheses we have used. We can backtrack if we reach a state where the number of open parentheses is greater than n or the number of close parentheses is greater than the number of open parentheses.

The time complexity of this approach is O(4^n / sqrt(n)), where n is the number of pairs of parentheses. The space complexity is O(n) to store the current combination of parentheses.

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

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

  • Add import statement if required.
  • Optimize the code for better time or space complexity.
  • Add test cases to validate edge cases and common scenarios.
  • Handle error conditions or invalid inputs gracefully.
  • Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Previous QuestionNext Question