# All Possible Braces

## Problem Statement

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

• Recursion

## Try it yourself

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

## Solution

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);}

## 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).

### 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: