instagram

Print all combinations of balanced parentheses – Java

by omt

For Example n =3 we want below O/P

[[[]]]
[[][]]
[[]][]
[][[]]
[][][]

For n = 2

[[]]
[][]

Just to get count of all possible combinations then it is very easy using Catalan number theory

Catalan number = 2n!/[(n+1)! * n!]

For n = 3 number of possible solutions are 5 as per Catalan number

Check more about Catalan Number

Algorithm :

package com.omt.learn.algo;

public class FindPossibleCombination {

	public static void main(String[] args) {

		int n = 3;

		combinations("", n, 0);

	}

	public static void combinations(String sb, int open, int close) {

		if (open == 0 && close == 0) {
			System.out.println(sb.toString());
		} else {

			if (open > 0) {
				combinations(sb + "[", open - 1, close + 1);
			}

			if (close > 0) {
				combinations(sb + "]", open, close - 1);
			}

		}

	}

}
Share