查找总和为 Python 中某个数字的唯一数字的方法的数量

Question

问题描述如下：

There is a list of integers, sequence. There is another integer argument, target. The objective is to return the number of unique ways target can be expressed as the sum of four distinct numbers in sequence.

这是我的代码：

def __main__(sequence, target):
    big = 0
    for elem in sequence:
        for elem_ in sequence:
            for _elem_ in sequence:
                for _elem__ in sequence:
                    if (elem + elem_ + _elem_ + _elem__ == target):
                        big+=1
    print(str(big))        
__main__([2, 1, 1, 1, 2, 1, 2, 2, 1], 6)

算法对我来说似乎很好。但是我一直得到这个答案2400，根据测试用例，答案应该是60。我怀疑我对一种方法进行了四次检查，但是再次将 2400 除以 4 不会给你 60.

Answer 1

这是一种方法：

def sums(sequence, target):
    n = len(sequence)
    total = 0

    for i1 in range(n):
        v1 = sequence[i1]
        for i2 in range(i1+1, n):
            v2 = sequence[i2]
            for i3 in range(i2+1, n):
                v3 = sequence[i3]
                for i4 in range(i3+1, n):
                    v4 = sequence[i4]
                    if v1+v2+v3+v4 == target:
                        total += 1

    return total

def main():
    print(sums([2, 1, 1, 1, 2, 1, 2, 2, 1], 6))

main()

这确保每个列表元素最多使用一次，并给出所需的结果 60。

循环没有我想要的那么简洁，但它很高效，并且不需要任何临时列表切片。

Answer 2

您可以使用 itertools.combinations():

import itertools

def sums(lst, n):
  count = 0

  for sample in list(itertools.combinations(lst, 4)):
    if sum(sample) == n:
      count += 1
  
  return count

print(sums([2, 1, 1, 1, 2, 1, 2, 2, 1], 6)) # => 60

来自文档：

Return r length subsequences of elements from the input iterable.

Combinations are emitted in lexicographic sort order. So, if the input iterable is sorted, the combination tuples will be produced in sorted order.

Elements are treated as unique based on their position, not on their value. So if the input elements are unique, there will be no repeat values in each combination.
combinations(range(4), 3) # --> 012 013 023 123

查找总和为 Python 中某个数字的唯一数字的方法的数量

The number of ways to find unique numbers that sum to a number in Python

python

python-3.5