Найдите количество трех сумм в списке

Question

Если вам дан список

numList = [1,2,3,4,5,6,7]

и вас попросят найти число из трех сумм, добавляемых к определенному номеру

target = 10

Как ты мог придумать ответ?

Например, комбинация: [1,3,6], [1,2,7], [2,3,5], [1,4,5] приведет к возвращаемому значению 4.

Я знаю, как использовать функцию, основанную на хешировании, чтобы придумать одну три сумму для решения, используя приведенный ниже код, но я не уверен, как добавить все уникальные три суммы решений.

def find3Numbers(A,arr_size,sum): 
    for i in range(0,arr_size-1): 
        #Find pair in subarray A[i+1..n-1]  
        # with sum equal to sum - A[i] 
        s = set() 
        curr_sum = sum - A[i] 
        for j in range(i+1,arr_size): 
            if (curr_sum - A[j]) in s: 
                print("Triplet is", A[i],  
                        ", ", A[j], ", ", curr_sum-A[j]) 
                return True
            s.add(A[j]) 

    return False

Answer 1

Использование itertools.combinsk

from itertools import combinations

numList = [1,2,3,4,5,6,7]

def check(value):
    return sum(value) == 10

filtered = list(filter(check, list(combinations(numList, 3))))
print(filtered)
#[(1, 2, 7), (1, 3, 6), (1, 4, 5), (2, 3, 5)]

Комбинации находит все возможные комбинации, тогда я просто отфильтровал их до тех, которые добавили до 10

Answer 2

Вам просто нужно настроить решение для подсчета решений, а не возвращать его после того, как найдено первое решение:

def find3Numbers(A,arr_size,sum):
    count_sums = 0

    for i in range(0,arr_size-1): 
        #Find pair in subarray A[i+1..n-1]  
        # with sum equal to sum - A[i] 
        s = set() 
        curr_sum = sum - A[i] 
        for j in range(i+1,arr_size): 
            if (curr_sum - A[j]) in s: 
                count_sums += 1 # Count here
            s.add(A[j]) 

    return count_sums # Finally return the count

---

Обратите внимание, это не означает, что ваш алгоритм теперь верен. Двигаясь дальше, вы можете использовать набор подсчета вместо обычного набора для s. См. collections.Counter.