python - 在 Python 上使用回溯的子集总和

Question

所以我想打印出初始集合的所有子集，这些子集加起来为 21。到目前为止，我只想到了这个

def twentyone(array, num=21):
    if len(array) == 0:
        return None
    else:
        if array[0] == num:
            return [array[0]]
        else:
            with_v = twentyone(array[1:], (num - array[0]))
            if with_v:
                return [array[0]] + with_v
            else:
                return twentyone(array[1:], num)

它确实给出了解决方案，但只是第一个。我如何更改它以便它给我所有可能的子集。我试过做一些改变，但它只给了我嵌套列表。你能帮忙的话，我会很高兴。

Answer 1

你可以创建一个递归生成器:

def twentyone(array, num=21):
    if num < 0:
        return
    if len(array) == 0:
        if num == 0:
            yield []
        return
    for solution in twentyone(array[1:], num):
        yield solution
    for solution in twentyone(array[1:], num - array[0]):
        yield [array[0]] + solution

例子:

>>> list(twentyone([5, 16, 3, 2]))
[[16, 3, 2], [5, 16]]