如何修正整数嵌套分划生成代码，解决结果重复问题？

需求与问题背景 #

需要生成整数n的所有嵌套分划，需覆盖所有数字排列及任意位置的括号嵌套。例如n=3时，期望得到以下6种结果：

(3,)
(1, 2)
(1, 1, 1)
(1, (1, 1))
(2, 1)
((1, 1), 1)

基于标准整数分划逻辑编写的代码会生成重复结果，比如n=3时(1,1,1)会被生成两次，根源在于拆分过程中存在重复分支（如拆分1+2和2+1时，均会生成扁平组合(1,1,1)）。

修正方案 #

通过引入集合记录已生成的分划结果，过滤重复项。修正后的代码如下：

def partitions(n):
    seen = set()
    
    def helper(k):
        # 生成单个数字的分划
        yield (k,)
        for i in range(1, k):
            for q in helper(i):
                for p in helper(k - i):
                    # 生成所有可能的组合形式
                    candidates = []
                    candidates.append(q + p)
                    if len(q) > 1:
                        candidates.append((q,) + p)
                    if len(p) > 1:
                        candidates.append(q + (p,))
                    if len(q) > 1 and len(p) > 1:
                        candidates.append((q,) + (p,))
                    
                    # 仅返回未出现过的分划
                    for candidate in candidates:
                        if candidate not in seen:
                            seen.add(candidate)
                            yield candidate
    
    yield from helper(n)

原理说明 #

• 引入seen集合存储已生成的嵌套分划元组（元组为不可变类型，可作为集合元素）。
• 每次生成新的分划组合时，先检查是否已存在于seen中，仅当未存在时才返回该分划并加入集合。
• 彻底避免了对称拆分（如i和n-i）导致的重复扁平组合问题，同时保留了所有需要的排列和嵌套形式。

测试验证 #

调用list(partitions(3))会得到与期望一致的6种无重复结果：

[(3,), (1, 2), (1, (1, 1)), (2, 1), ((1, 1), 1), (1, 1, 1)]

内容的提问来源于stack exchange，提问作者Jake B.