如何在O（n^2）中找到给定数组中每个可能的三元组的和？

Question

我有这样一个数组：

1,2,3,4,5。

我想找出每一个可能的三元组的总和，比如：123、124、125、134、135等等

我曾尝试使用3个while循环和3个变量（I，j，k）迭代每个三元组，但时间复杂度是O（n^3），我希望是O（n^2）。

希望有人来帮忙。

Answer 1

Python有一个内置的方法来做这件事。

时间复杂度：itertools的计算复杂度是多少。python中的组合？

代码：

import itertools
print(list(itertools.combinations(range(1,6),3)))

结果：

[(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)]

如果你需要一笔钱

代码：

import itertools
print(sum([int(''.join(map(str,x))) for x in list(itertools.combinations(range(1,6),3))]))

结果：

1845

Answer 2

n的k置换？我的第一次尝试是这样的，因为数组类似于[1,2,3，…，n，n1]，并且3的和将重复：

unique_sums = set()

iter_counter = [0]
call_counter = [0]
def sum_permute(arr, perm, k):
    call_counter[0] += 1
    result = sum(perm)
    if result in unique_sums:
        return
    if len(perm) == k:
        iter_counter[0] += 1
        # print(f"sum{perm}={result}")
        unique_sums.add(result)
        return
    for el in arr:
        iter_counter[0] += 1
        if el not in perm:
            perm.add(el)
            sum_permute(arr, perm, k)
            perm.pop()

如果不丢弃重复的和，则在n（n-1）（n-2）。。。（n-k1），k=3，~O（n^3），假设在集合中查找beO（1）。无论如何，结果如下：

arr = [el for el in range(100)]
sum_permute(arr ,set(), 3)
print(f"Total elements: {len(arr)}")
print(f"Total iterations: {iter_counter[0]}")
print(f"Total function call: {call_counter[0]}")
print(f"n^2={len(arr)}^2={len(arr)**2}")

结果:

Total elements: 100
Total iterations: 3372
Total function call: 3091
n^2=100^2=10000