三个数字的组合总和为 1000

Question

我需要总和为 1000的三个正整数的每个组合。

这是我的尝试，但我不确定这是否正确，因为我无法验证它。

def getSum():

    l = []

    for x in range(1, 999):

        total = 1000-x

        for y in range(1, 999):

            total = total-y

            if total>0:

                l.append([x, y, total])

    return l

print len(getSum())

我得到 28776 种不同的组合。那是对的吗？

Answer 1

由于1+998+1和1+1+998是不一样的东西，也有组合的一些不可思议的量：这一行可以生成它们：[(i, 1000-i-k, k) for i in range(1,999) for k in range(1,1000-i)]结果：[...(1, 4, 995),(1, 3, 996),(1, 2, 997),(1, 1, 998),(2, 997, 1),(2, 996, 2),...]这个列表的长度是：498501

Answer 2

不，那个数字不正确。您的代码的问题是这一行：&nbsp; &nbsp; &nbsp; &nbsp; total = total-y在这里，您尝试的total每个值都越来越小y，永远不要将其重置为减去后的值x。要修复它，请创建一个新变量，例如total2，并在内部循环中使用它。&nbsp; &nbsp; &nbsp; &nbsp; total2 = total-y这样，您就可以获得498501组合。此外，您可以break尽快从内部循环total2 < 0。如果您只需要组合的数量：请注意，存在将N-1两个数字相加到的组合N，例如对于N==4: 1+3, 2+2, 3+1（假设您考虑1+3和3+1不同）。您可以将此扩展到三个数字的情况，将数字分成两部分两次。这样，您只需要一个循环。这可以进一步简化为 O(1) 公式。示例，使用天真的方法product作为参考：>>> N = 100&nbsp; # to make reference faster>>> sum(1 for t in product(range(1, N+1), repeat=3) if sum(t)==N)4851>>> sum(N-1-i for i in range(1, N-1))4851>>> ((N-2)*(N-1))//24851当然，也适用于N = 1000（或更大，更大）：>>> N = 1000>>> sum(N-1-i for i in range(1, N-1))498501>>> ((N-2)*(N-1))//2498501

Answer 3

如果你处理 [1,1,998] 和 [1,998,1] 相同（没有唯一的整数）：def getSum():&nbsp; &nbsp; l = []&nbsp; &nbsp; for x in range(1, 999):&nbsp; &nbsp; &nbsp; &nbsp; total = 1000-x&nbsp; &nbsp; &nbsp; &nbsp; for y in range(1, 999):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; total = total-y&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if total>0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; z = [x, y, total]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; z.sort()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if z not in l:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l.append(z)return la = getSum()print(len(a))如果你想要 3 个唯一的整数：def getSum():&nbsp; &nbsp; l = []&nbsp; &nbsp; for x in range(1, 999):&nbsp; &nbsp; &nbsp; &nbsp; total = 1000-x&nbsp; &nbsp; &nbsp; &nbsp; for y in range(1, 999):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; total = total-y&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if total>0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; z = [x, y, total]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; z.sort()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (z not in l) and (not((len(set(z)) < len(z)))):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l.append(z)&nbsp; &nbsp; return la = getSum()print(len(a))否则你的代码（在我的意义上）没问题。我还没有检查你的答案...编辑：我用野蛮的力量检查过它。如果您以不同的方式处理 (1,1,998) 和 (998,1,1)，则正确答案实际上是 498501。目前不知道为什么...