list - 加起来为 21 的列表的子序列

Question

使用 Python，我将如何返回一个加起来为 21 的正整数列表的子序列。

例如，对于列表：

x = [5, 6, 7, 10, 11]

子序列将是：

[[5, 6, 10], [10, 11]]

任何帮助，将不胜感激。

Answer 1

您可以使用生成所有可能的情况来执行此操作，尽管对于大量元素（即列表中的 n 个元素）Backtracking来说复杂性会很高。O(2^n)

在递归调用中的每个索引处，我们可以选择当前元素或选择忽略它，从而遍历所有可能的情况。

蟒蛇代码：

list = [5, 6, 7, 10, 11]

def solve(index, sum, ans):
    if(index == len(list)):
        if(sum == 21):
            print(*ans)
    else:
        ans.append(list[index])
        solve(index+1, sum+list[index], ans)
        ans.pop(-1)
        solve(index+1, sum, ans)

ans = []
solve(0, 0, ans)

Ideone 上的解决方案链接：http: //ideone.com/P5HnfU