โปรแกรมหาจำนวน quadruple ที่แตกต่างกันให้ผลรวมเท่ากับ target ใน Python

มี 4 รายการ A,B,C,D และ target หาจำนวน quadruple (i,j,k,l) ที่ A[i]+B[j]+C[k]+D[l] = target

เช่น A=[5,4,3] B=[8,4] C=[6,2] D=[4,10] target=23 ให้ 3

ขั้นตอนการแก้ปัญหา

• Meet-in-the-middle: คำนวณผลรวม A+B ทุกคู่ เก็บความถี่ใน m
• วนทุกคู่ C+D: หา target - (C[k]+D[l]) ใน m
• รวมความถี่

ตัวอย่างโค้ด

class Solution:
    def solve(self, A, B, C, D, target):
        count = 0
        from collections import defaultdict
        m = defaultdict(int)
        for i in A:
            for j in B: m[i+j] += 1
        for k in C:
            for z in D:
                if target - (k+z) in m:
                    count += m[target - (k+z)]
        return count

ob = Solution()
A = [5,4,3]; B = [8,4]; C = [6,2]; D = [4,10]; target = 23
print(ob.solve(A, B, C, D, target))

อินพุต

[5, 4, 3], [8, 4], [6, 2], [4, 10], 23

เอาต์พุต

3