hard Balanced Parentheses

Problem Statement

For a given number ‘N’, write a function to generate all combination of ‘N’ pairs of balanced parentheses.

Example 1:

Input: N=2
Output: (()), ()()

Example 2:

Input: N=3
Output: ((())), (()()), (())(), ()(()), ()()()

Constraints:

1 <= n <= 8

Try it yourself

Try solving this question here:

✅ Solution Balanced Parentheses

Problem Statement

For a given number ‘N’, write a function to generate all combination of ‘N’ pairs of balanced parentheses.

Example 1:

Input: N=2
Output: (()), ()()

Example 2:

Input: N=3
Output: ((())), (()()), (())(), ()(()), ()()()

Constraints:

1 <= n <= 8

Solution

This problem follows the Subsets pattern and can be mapped to Permutations. We can follow a similar BFS approach.

Let’s take Example-2 mentioned above to generate all the combinations of balanced parentheses. Following a BFS approach, we will keep adding open parentheses ( or close parentheses ). At each step we need to keep two things in mind:

We can’t add more than ‘N’ open parenthesis.
To keep the parentheses balanced, we can add a close parenthesis ) only when we have already added enough open parenthesis (. For this, we can keep a count of open and close parenthesis with every combination.

Following this guideline, let’s generate parentheses for N=3:

Start with an empty combination: “”
At every step, let’s take all combinations of the previous step and add ( or ) keeping the above-mentioned two rules in mind.
For the empty combination, we can add ( since the count of open parenthesis will be less than ‘N’. We can’t add ) as we don’t have an equivalent open parenthesis, so our list of combinations will now be: “(”
For the next iteration, let’s take all combinations of the previous set. For “(” we can add another ( to it since the count of open parenthesis will be less than ‘N’. We can also add ) as we do have an equivalent open parenthesis, so our list of combinations will be: “((”, “()”
In the next iteration, for the first combination “((”, we can add another ( to it as the count of open parenthesis will be less than ‘N’, we can also add ) as we do have an equivalent open parenthesis. This gives us two new combinations: “(((” and “(()”. For the second combination “()”, we can add another ( to it since the count of open parenthesis will be less than ‘N’. We can’t add ) as we don’t have an equivalent open parenthesis, so our list of combinations will be: “(((”, “(()”, ()("
Following the same approach, next we will get the following list of combinations: “((()”, “(()(”, “(())”, “()((”, “()()”
Next we will get: “((())”, “(()()”, “(())(”, “()(()”, “()()(”
Finally, we will have the following combinations of balanced parentheses: “((()))”, “(()())”, “(())()”, “()(())”, “()()()”
We can’t add more parentheses to any of the combinations, so we stop here.

Here is the visual representation of this algorithm:

Code

Here is what our algorithm will look like:

java

import java.util.*;

class ParenthesesString {

  String str;
  int openCount; // open parentheses count
  int closeCount; // close parentheses count

  public ParenthesesString(String s, int openCount, int closeCount) {
    str = s;
    this.openCount = openCount;
    this.closeCount = closeCount;
  }
}

class Solution {

  public List<String> generateValidParentheses(int num) {
    List<String> result = new ArrayList<String>();
    Queue<ParenthesesString> queue = new LinkedList<>();
    queue.add(new ParenthesesString("", 0, 0));
    while (!queue.isEmpty()) {
      ParenthesesString ps = queue.poll();
      // if we've reached the maximum number of open and close parentheses, add to result
      if (ps.openCount == num && ps.closeCount == num) {
        result.add(ps.str);
      } else {
        if (
          ps.openCount < num
        ) queue.add( // if we can add an open parentheses, add it
          new ParenthesesString(ps.str + "(", ps.openCount + 1, ps.closeCount)
        );

        if (
          ps.openCount > ps.closeCount
        ) queue.add( // if we can add a close parentheses, add it
          new ParenthesesString(ps.str + ")", ps.openCount, ps.closeCount + 1)
        );
      }
    }
    return result;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    List<String> result = sol.generateValidParentheses(2);
    System.out.println(
      "All combinations of balanced parentheses are: " + result
    );

    result = sol.generateValidParentheses(3);
    System.out.println(
      "All combinations of balanced parentheses are: " + result
    );
  }
}

Time Complexity

Let’s try to estimate how many combinations we can have for ‘N’ pairs of balanced parentheses. If we don’t care for the ordering that ) can only come after (, then we have two options for every position, i.e., either put open parentheses or close parentheses. This means we can have a maximum of combinations. Because of the ordering, the actual number will be less than .

If you see the visual representation of Example-2 closely you will realize that, in the worst case, it is equivalent to a binary tree, where each node will have two children. This means that we will have leaf nodes and intermediate nodes. So the total number of elements pushed to the queue will be , which is asymptotically equivalent to . While processing each element, we do need to concatenate the current string with ( or ). This operation will take , so the overall time complexity of our algorithm will be . This is not completely accurate but reasonable enough to be presented in the interview.

The actual time complexity is bounded by the Catalan number and is beyond the scope of a coding interview. See more details here.

Space Complexity

All the additional space used by our algorithm is for the output list. Since we can’t have more than combinations, the space complexity of our algorithm is .

Recursive Solution

Here is the recursive algorithm following a similar approach:

java

import java.util.*;

class Solution {

  public List<String> generateValidParentheses(int num) {
    List<String> result = new ArrayList<String>();
    char[] parenthesesString = new char[2 * num];
    generateValidParenthesesRecursive(num, 0, 0, parenthesesString, 0, result);
    return result;
  }

  private static void generateValidParenthesesRecursive(int num, int openCount, 
        int closeCount, char[] parenthesesString, int index, List<String> result) {

    // if we've reached the maximum number of open and close parentheses, add to result
    if (openCount == num && closeCount == num) {
      result.add(new String(parenthesesString));
    } else {
      if (openCount < num) { // if we can add an open parentheses, add it
        parenthesesString[index] = '(';
        generateValidParenthesesRecursive(num, openCount + 1, closeCount, 
                                          parenthesesString, index + 1, result);
      }

      if (openCount > closeCount) { // if we can add a close parentheses, add it
        parenthesesString[index] = ')';
        generateValidParenthesesRecursive(num, openCount, closeCount + 1, 
                                          parenthesesString, index + 1, result);
      }
    }
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    List<String> result = sol.generateValidParentheses(2);
    System.out.println("All combinations of balanced parentheses are: " + result);

    result = sol.generateValidParentheses(3);
    System.out.println("All combinations of balanced parentheses are: " + result);
  }
}

🤖 Don't fully get this? Learn it with Claude

Stuck on Balanced Parentheses? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Balanced Parentheses** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Balanced Parentheses** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Balanced Parentheses**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Balanced Parentheses**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Letter Combinations of a Phone Num Palindromic Partitioning →