为什么我尝试回溯解决平衡括号问题不起作用？

Question

我不确定我对回溯有什么误解。

问题：

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

示例 1：

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

示例 2：

Input: n = 1
Output: ["()"]

约束条件：

1 <= n <= 8

到目前为止我尝试过的（工作代码）：

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

对于所有情况，代码似乎 return 空数组。

Answer 1

我不确定是否需要额外的复杂功能。我们可以有一个递归来保持跟踪并且在构造期间的任何时候都不让右括号 (r) 的计数超过左括号 (n) 的计数：

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)))

为什么我尝试回溯解决平衡括号问题不起作用？

Why does my attempt at backtracking to solve the balanced parentheses problem not work?

python

algorithm

backtracking