I'm not sure what I'm misunderstanding about backtracking.
Problem:
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]
Constraints:
1 <= n <= 8
What I've tried so far (working code):
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
balanced = []
placement = []
left = [')'] * n
right = ['()'] * n
def is_balanced(placement):
open_list = ["[","{","("]
close_list = ["]","}",")"]
myStr = placement[0]
stack = []
for i in myStr:
if i in open_list:
stack.append(i)
elif i in close_list:
pos = close_list.index(i)
if ((len(stack) > 0) and
(open_list[pos] == stack[len(stack)-1])):
stack.pop()
else:
return False
if len(stack) == 0:
return True
else:
return False
def solve(left, right, results):
#goal or base case
if len(left) == 0 or len(right) == 0:
balanced.extend(results)
return
for i in range(2*n):
l = left.pop(0)
placement.append(l)
if is_balanced(placement):
#recurse on decision
solve(left, right, results)
r = right.pop(0)
placement.append(r)
if is_balanced(placement):
#recurse on decision
solve(left, right, results)
#undo decision
left.append(l)
right.append(r)
placement.pop(-1)
solve(left, right, results)
return balanced
The code seems to return empty array for all cases.
I'm not sure if the extra complication is necessary. We can have a recursion that keeps track and doesn't let the count of right parentheses (r) exceed the count of the left (n) at any point during the construction:
function f(n, s='', r=n){
return r == 0 ? [s] : (n == 0 ? [] : f(n-1, s+'(', r))
.concat(r > n ? f(n, s+')', r-1) : [])
}
console.log(JSON.stringify(f(3)))