【每日一题0725】生成括号

兴趣爱好交流 每日一题
1

:woman_mage:数字 n 代表生成括号的对数，请编写一个python函数，接收数字n，返回所有可能的并且有效的括号组合。

示例：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

题目难度：中等
题目来源：力扣 22

def generate(n:int):
    pass
    
assert sorted(generate(3)) == sorted(["((()))","(()())","(())()","()(())","()()()"])
assert sorted(generate(1)) == sorted(["()"])
2

写不出来，看答案都想不明白？ 求高手解释 :sweat_smile:

3 
def generate(n: int):
    def iter_(ns):
        if ns == 1:  # n = 1递归结束
            yield "()"
        else:
            last_result = list(iter_(ns - 1))
            # 第一种情况在前面
            for i in last_result:
                yield "()" + i
            # 第二种情况包含
            for i in last_result:
                yield "(" + i + ")"
            # 第三种情况在右边
            for i in last_result:
                if i != "()" * (ns - 1): # 去掉对称的情况
                    yield i + "()"

    return list(iter_(n))


assert sorted(generate(3)) == sorted(["((()))", "(()())", "(())()", "()(())", "()()()"])
assert sorted(generate(1)) == sorted(["()"])
1 个赞
4 
def generate(n: int):
    if n == 0: return
    res = []

    def dfs(paths, left, right):
        if left > n or right > left: return
        if len(paths) == n * 2:
            res.append(paths)
            return
        dfs(paths + "(", left + 1, right)
        dfs(paths + ")", left, right + 1)

    dfs("", 0, 0)
    return res


assert sorted(generate(3)) == sorted(["((()))", "(()())", "(())()", "()(())", "()()()"])
assert sorted(generate(1)) == sorted(["()"])
1 个赞
6

你这种写法，如果输入的n是4的话，就漏掉了’(())(())'这种情况，就是说还有情况漏掉了

7 
def generate(n: int):
    left_n = n
    right_n = n

    def iter_(left_ns, right_ns, r=""):
        if left_ns == 0 and right_ns == 1:  # 右边括号n = 1递归结束
            yield r + ")"
        else:
            # 如果左边n用完,或者左边的括号没有被先使用
            if left_ns == 0:
                yield from iter_(left_ns, right_ns - 1, r + ")")
            else:
                if left_ns == right_ns:  # 如果左右边剩下的括号相等先使用左边的
                    yield from iter_(left_ns - 1, right_ns, r + "(")
                else:
                    yield from iter_(left_ns - 1, right_ns, r + "(")
                    yield from iter_(left_ns, right_ns - 1, r + ")")

    return list(iter_(left_n, right_n))


assert sorted(generate(3)) == sorted(["((()))", "(()())", "(())()", "()(())", "()()()"])
assert sorted(generate(1)) == sorted(["()"])
print(generate(4))

你说的对，这样递归思路确实有问题，如果把左右括号分开看呢

8

这种就可以了

10

为啥两种方法的返回的长度一致。

11

因为之前的那种没有去掉前后有完整括号的情况（有重复数据），算了总长度了，凑巧两长度一致了

12

谢谢大佬解惑。

这个的本质是栈和回溯吧，然后优化。

13 
def generate(n: int):
    s_list = []
    start_list = ['('] * n + [')'] * n
    res_set = set(itertools.permutations(start_list, n * 2))
    res_list = [''.join(item) for item in res_set]
    for i in res_list:
        s = 0
        valid = True
        for j in i:
            if j == '(':
                s += 1
            elif j == ')':
                s -= 1
            if s < 0:
                valid = False
                break
        if valid and s == 0:
            s_list.append(i)
    return s_list


assert sorted(generate(3)) == sorted(["((()))", "(()())", "(())()", "()(())", "()()()"])
assert sorted(generate(1)) == sorted(["()"])