Print all combinations of balanced parentheses – Java
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); } } } }