# Problem Statement
Print all braces combinations for a given value n so that they are balanced. Here are a few examples:

<br>

# Hint
* Recursion

<br>

# Try it yourself

vector<vector<char>> print_all_braces(int n) {
  //TODO: Write - Your - Code
  vector<vector<char>> result;
  return result;
}

#include <iostream>
#include <vector>
#include <string>

using namespace std;



string printcpy(vector<vector<char>> result){
  string aa;
  for(int i = 0; i < result.size(); i++){
    cout << "[ ";
    aa += "[ ";
    for(int j = 0; j < result[i].size(); j++){
      cout << result[i][j] << ", "; 
      aa += result[i][j];
      aa += ", ";
    }
    aa += "]";
    cout << "]" << endl;
  }
  return aa;
}

class AllBraces{
  static ArrayList<ArrayList<Character>> printAllBraces(int n) {
    ArrayList<ArrayList<Character>> result = new ArrayList<ArrayList<Character>>();
    //TODO: Write - Your - Code
    return result;
  }
} 

import java.util.*;
import java.lang.*;

@SuppressWarnings("unchecked")

Java

def print_all_braces(n):
  #TODO: Write - Your - Code
  result = []
  return result

Python

let printAllBraces = function(n) {
 // TODO: Write - Your - Code
  let result = [];
  return result;
};

JavaScript

def print_all_braces(n)
# TODO: Write - Your - Code
  result = []
  return result
end

Ruby

void print(vector<vector<char>> result){
  for(int i = 0; i < result.size(); i++){
    cout << "[ ";
    for(int j = 0; j < result[i].size(); j++){
      cout << result[i][j] << ", "; 
    }
    cout << "]" << endl;
  }
}

void print_all_braces_rec(
    int n,
    int left_count,
    int right_count,
    vector<char>& output, vector<vector<char>>& result) {

  if (left_count == n && right_count == n) {
    result.push_back(output);
  }

  if (left_count < n) {
    output.push_back('{');
    print_all_braces_rec(n, left_count + 1, right_count, output, result);
    output.pop_back();
  }

  if (right_count < left_count) {
    output.push_back('}');
    print_all_braces_rec(n, left_count, right_count + 1, output, result);
    output.pop_back();
  }
}

vector<vector<char>> print_all_braces(int n) {
  vector<vector<char>> result;
  vector<char> output;
  print_all_braces_rec(n, 0, 0, output, result);
  return result;
}

int main() {
  vector<vector<char>> result = print_all_braces(3);
  print(result);
}

class AllBraces{
  static void print(ArrayList<ArrayList<Character>> arr) {
    for (int i = 0; i < arr.size(); i++) {
      System.out.println(arr.get(i).toString());
    }
  }

  static void printAllBacesRec(
    int n,
    int leftCount,
    int rightCount, ArrayList<Character> output,
    ArrayList<ArrayList<Character>> result) {

    if (leftCount >= n && rightCount >=n) {
      result.add((ArrayList)output.clone());
    }

    if (leftCount < n) {
      output.add('{');
      printAllBacesRec(n, leftCount + 1, rightCount, output, result);
      output.remove(output.size() - 1);
    }

    if (rightCount < leftCount) {
      output.add('}');
      printAllBacesRec(n, leftCount, rightCount + 1, output, result);
      output.remove(output.size() - 1);
    }
  }

  static ArrayList<ArrayList<Character>> printAllBraces(int n) {
    ArrayList<ArrayList<Character>> result = new ArrayList<ArrayList<Character>>();
    ArrayList<Character> output = new ArrayList<Character>();
    printAllBacesRec(n, 0, 0, output, result);
    return result;
  }
  
  public static void main(String[] args) {
    ArrayList<ArrayList<Character>> result = new ArrayList<ArrayList<Character>>();
    result =  printAllBraces(3);
    print (result);
  }
}  

def print_all_braces_rec(n, left_count, right_count, output, result):

  if left_count >= n and right_count >= n:
    result.append(copy.copy(output));
    
  if left_count < n:
    output += '{'
    print_all_braces_rec(n, left_count + 1, right_count, output, result)
    output.pop()

  if right_count < left_count:
    output += '}'
    print_all_braces_rec(n, left_count, right_count + 1, output, result)
    output.pop()

def print_all_braces(n):
  output = []
  result = []
  print_all_braces_rec(n, 0, 0, output, result)
  return result

result = print_all_braces(3)

for rs in result: 
  print(rs)

def print_all_braces_rec(n, left_count, right_count, output, result)

  if (left_count >= n && right_count >= n)
    result.push (output.dup)
  end

  if (left_count < n)
    output.push('{')
    print_all_braces_rec(n, left_count + 1, right_count, output, result)
    output.pop()
  end
  if (right_count < left_count)
    output.push('}')
    print_all_braces_rec(n, left_count, right_count + 1, output, result)
    output.pop()
  end
end

def print_all_braces(n)
  output = []
  result = []
  print_all_braces_rec(n, 0, 0, output, result)
  return result
end

result = print_all_braces(3)
for rs in result do
  print rs
  puts
end

# Solution Explanation
## Runtime complexity
The runtime complexity of this solution is exponential, $2^{n}$

## Memory complexity
The memory complexity of this solution is linear, O(n).

<br>

## Solution Breakdown

The solution is to maintain counts of `left_braces` and `right_braces`. The basic algorithm is as follows:​

```
left_braces count: 0
right_braces count: 0
 
if left_braces count is less than n:
  add left_braces and recurse further
if right_braces count is less than left_braces count:
  add right_braces and recurse further
stop recursing when left_braces and right_braces counts are both equal to n
```


> Practice problems like this and many more by checking out our [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) course!

Print all balanced braces combinations for a given value 'n'.

All Possible Braces

Problem Statement

Hint

Try it yourself

Solution

Solution Explanation

Runtime complexity

Memory complexity

Solution Breakdown