Balanced parentheses
Given an integer ‘N’ representing the number of pairs of parentheses, Find all the possible combinations of balanced parentheses with the given number of pairs of parentheses.

Note :

Conditions for valid parentheses: 1. All open brackets must be closed by the closing brackets. 2. Open brackets must be closed in the correct order.

For Example :

()()()() is a valid parentheses. )()()( is not a valid parentheses.

Input format :

The first line of input contains an integer ‘T’, which denotes the number of test cases. Then each test case follows. Each line of the test case contains an integer ‘N’ denoting the pair of parentheses.

Output format :

For each test case print, all the combinations of balanced parentheses separated by a single space. The output of each test case will be printed on a separate line.

Note:

1. You don't need to print anything, it has already been taken care of. Just implement the given function. 2. You can return strings in any order.

Constraints:

1

Question

Balanced parentheses

Given an integer ‘N’ representing the number of pairs of parentheses, Find all the possible combinations of balanced parentheses with the given number of pairs of parentheses.

Note :

Conditions for valid parentheses:
1. All open brackets must be closed by the closing brackets.

2. Open brackets must be closed in the correct order.

For Example :

()()()() is a valid parentheses.
)()()( is not a valid parentheses.

Input format :

The first line of input contains an integer ‘T’, which denotes the number of test cases. Then each test case follows.

Each line of the test case contains an integer ‘N’ denoting the pair of parentheses.

Output format :

For each test case print, all the combinations of balanced parentheses separated by a single space.

The output of each test case will be printed on a separate line.

Note:

1. You don't need to print anything, it has already been taken care of. Just implement the given function.

2. You can return strings in any order.

Constraints:

1 <= T <= 5
1 <= N <= 10
Time Limit : 1 sec.

Accepted Answer

A stack can be used to solve this question.
We traverse the given string s and if we:
1. see open bracket we put it to stack
2. see closed bracket, then it must be equal to bracket in the top of our stack, so we check it and if it is true, we remove this pair of brackets.
3. In the end, if and only if we have empty stack, we have valid string.
Complexity: time complexity is O(n): we put and pop each element of string from our stack only once. Space complexity is O(n).

Accepted Answer

Recursion

The idea is to generate all possible combinations and check whether the combination is the combination of balanced parentheses or not. We have two choices whether to consider ‘(‘ or ‘)’.

When the number of closing brackets is greater than the number of opening brackets we can consider taking ‘)’ in the sequence and in the other case we can consider taking ‘(‘ for all numbers of opening brackets until the number of opening brackets becomes 0. We get the required sequence when we leave with no count of opening and closing brackets.

Recursive tree for N = 2 is shown below representing output string, number of open brackets and number of closing brackets

Algorithm :

First make a recursive function, say ‘solve’ taking the number of opening brackets ‘opening’, number of closing brackets ‘closing’ output string ‘output’, and an array of strings ‘ans’ as arguments.
Make the base condition as if ‘opening’ = 0 and ‘closing’ = 0 then push the output string in the ‘ans’ and return.
If ‘opening’ is not equal to zero then call the ‘solve’ function recursively by decrementing ‘opening’ by 1 and inserting ‘(‘ into the ‘output’.
If ‘closing’ > ‘opening’ then call the ‘solve’ function recursively by decrementing ‘closing’ by 1 and inserting ‘)’ into the ‘output’.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the given integer.

As we are using extra space for storing the combinations in the string of length ‘2 * N’. Therefore, the overall space complexity will be O(N).

Time Complexity: O(2^n)Explanation:

O(2 ^ N), where ‘N’ is the given integer.

As we are making two choices whether to take ‘(‘ or not and whether to take ‘)’ or not ‘N’ number of times which makes the operation 2 ^ N times. Therefore, the overall time complexity will be O(2 ^ N).

Java (SE 1.8)


/*
	Time Complexity: O(2 ^ N)
	Space Complexity: O(N)
	
	Where 'N' denotes the number of paires of parantheses.
*/

import java.util.ArrayList;
import java.util.List;

public class Solution {

	public static List balancedParantheses(int n) {

		// Declare a array of string to store all the balanced strings.
		List ans = new ArrayList<>();
		String output = "";

		solve(ans, output, n, n);

		return ans;

	}

	// Recursive Function.
	private static List solve(List ans, String output, int opening, int closing) {

		// If we are left with 0 opening and closing braces.
		if (opening == 0 && closing == 0) {

			// Push the entire string in the vector.
			ans.add(output);
			return ans;
		}

		// If we have opening brackets we can insert the '(' in every case.
		if (opening != 0) {
			solve(ans, output + '(', opening - 1, closing);
		}

		/*
		 * If number of closing brackets > number of opening brackets means we have used
		 * more opening brackets than closing brackets.
		 */
		if (closing > opening) {
			solve(ans, output + ')', opening, closing - 1);
		}

		return ans;

	}

}

Python (3.5)

'''

    Time Complexity: O(2 ^ N)

    Space Complexity: O(N)

    

    Where 'N' denotes the number of paires of parantheses.

'''



# Recursive Function.

def solve(ans, output, opening, closing):

	

	# If we are left with 0 opening and closing braces.

	if(opening == 0 and closing == 0):

		

		# Push the entire string in the vector.

		ans.append(output)

		return



	# If we have opening brackets we can insert the '(' in every case.

	if(opening != 0):

		solve(ans, output + '(', opening - 1, closing)

		

	'''

        If number of closing brackets > number of opening brackets

        means we have used more opening brackets than closing brackets.

	'''

	if(closing > opening):

		solve(ans, output + ')', opening, closing - 1)

		

	return





def balancedParantheses(n):



	# Declare a array to store all the strings.

	ans = []



	# Initialize empty string.

	output = ""



	# Call recursive function.

	solve(ans, output, n, n)

	

	return ans

C++ (g++ 5.4)

/*

    Time Complexity: O(2 ^ N)

    Space Complexity: O(N)

    

    Where 'N' denotes the number of paires of parantheses.

*/



// Recursive Function.

void solve(vector &ans, string output, int opening, int closing)

{

    

    // If we are left with 0 opening and closing braces.

    if(opening == 0 && closing == 0)

    {

        

        // Push the entire string in the vector.

        ans.push_back(output);

        return;

    }



    // If we have opening brackets we can insert the '(' in every case.

    if(opening != 0)

    {

        solve(ans, output + '(', opening - 1, closing);

    }



    /*

        If number of closing brackets > number of opening brackets

        means we have used more opening brackets than closing brackets.

    */

    if(closing > opening)

    {

        solve(ans, output + ')', opening, closing - 1);

    }

    

    return;

}



vector balancedParantheses(int n)

{

    // Declare a array of string to store all the balanced strings.

    vector ans;

    string output = "";



    solve(ans, output, n, n);



    return ans;

}