三个数字的组合总和为 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 lprint 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

不，那个数字不正确。您的代码的问题是这一行：

        total = total-y

在这里，您尝试的total每个值都越来越小y，永远不要将其重置为减去后的值x。要修复它，请创建一个新变量，例如total2，并在内部循环中使用它。

        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  # 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))//2

4851

当然，也适用于N = 1000（或更大，更大）：

>>> N = 1000

>>> sum(N-1-i for i in range(1, N-1))

498501

>>> ((N-2)*(N-1))//2

498501

Answer 3

如果你处理 [1,1,998] 和 [1,998,1] 相同（没有唯一的整数）：

def getSum():

    l = []

    for x in range(1, 999):

        total = 1000-x

        for y in range(1, 999):

            total = total-y

            if total>0:

                z = [x, y, total]

                z.sort()

                if z not in l:

                    l.append(z)

return l

a = getSum()

print(len(a))

如果你想要 3 个唯一的整数：

def getSum():

    l = []

    for x in range(1, 999):

        total = 1000-x

        for y in range(1, 999):

            total = total-y

            if total>0:

                z = [x, y, total]

                z.sort()

                if (z not in l) and (not((len(set(z)) < len(z)))):

                    l.append(z)

    return l

a = getSum()

print(len(a))

否则你的代码（在我的意义上）没问题。我还没有检查你的答案...

编辑：我用野蛮的力量检查过它。如果您以不同的方式处理 (1,1,998) 和 (998,1,1)，则正确答案实际上是 498501。目前不知道为什么...