从一个数字列表中找出所有不同和的算法

Question

示例输入：

4 6 4 3 2 2 1 1

第二个数=数的个数，S(S<=12)

S numbers=这些数字的值（每个值<100)。（重复可能发生，输入按非递增顺序给出）

我的工作是使用列表中加起来等于T的数字来找到所有“不同的和”。

4
3+1
2+2
2+1+1

等等。

1. 我不确定这个算法是否有效
2. 我在实现该算法方面遇到了困难。我不能把我的头缠在如何循环结构以便得到想要的组合上。

Answer 1

您应该尝试一个递归解决方案。主要是，你只需要考虑到，对于每一个数字，你可以把它包括在你的总和中，也可以不包括。这意味着您正在构建数字的幂集，并将得到O(2^n)解决方案。

简单地用伪代码表示：

def get_all_sums(arr, target):

    result = []

    def helper(index, current_arr, current_sum):

        # once you've gone over the arr you can return. If all your numbers are positive
        # you can also return early if the current_sum > target
        if index == len(arr): return

        # solution found - add it to the result
        if current_sum == target: result.append(current_arr)

        # include the current index
        helper(index + 1, current_arr + [arr[index]], current_sum + arr[index])

        # don't include the current index
        helper(index + 1, current_arr, current_sum)

    helper(0, [], 0)

    # sort and hash to get rid of duplicates; return a set
    return {tuple(sorted(i) for i in result)}