class Solution { public List<String> generateParenthesis(int n) { /* you can find how many total no. of brackets will be generated through catalan number TC for interview purposes - O(n * 2^2n) */ backtrack("" , 0 , 0 , n); return res; } public List<String> res = new ArrayList<>(); //open -> open brackets , clost brackets public void backtrack(String sb , int open , int close , int n){ //base condition if(sb.length() == 2*n){ res.add(sb); return; } //always start with open bracket if(open < n) backtrack(sb + "(", open + 1 , close , n); //close brackets should always be lesser than open,make recursion //tree to understand this better if(close < open) backtrack(sb + ")",open ,close+1 , n); } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter