[Question]: Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example: – n = 2. — [“(())”, “()()”]
Approach: We can solve using backtracking / recursion
func backtrack(_ current: String,_ open: Int,_ end: Int,_ max: Int, _ result: inout [String]) {
if current.count == max * 2 {// Because if n = 2; max parenthesis count is (()) which is n X 2
result.append(current)
print("Brackets match ------ ", current)
return
}
if open < max {// Example: (( < 2 -- False So don't add open braces
print("open < max -- Open Bracket-- ", open+1, end, current + "(")
backtrack(current + "(", open + 1, end, max, &result)
}
print(" ")
if end < open {
print("end < open -- Open Bracket-- ", open+1, end, current + ")")
backtrack(current + ")", open, end + 1, max, &result)
}
}
let generateParath = generateParenthesis(2)
print("parathesis--- ", generateParath)// Ip::1 -> () Ip::2->()() (()) Ip::3-> ((()))", "(()())", "(())()", "()(())", "()()()
Logs --
open < max -- Open Bracket-- 1 0 (
open < max -- Open Bracket-- 2 0 ((
end < open -- Open Bracket-- 3 0 (()
end < open -- Open Bracket-- 3 1 (())
Brackets match ------ (())
end < open -- Open Bracket-- 2 0 ()
open < max -- Open Bracket-- 2 1 ()(
end < open -- Open Bracket-- 3 1 ()()
Brackets match ------ ()()
parentheses--- ["(())", "()()"] // Final output