Tìm cặp phần tử tổng cho trước từ các hàng khác nhau trong ma trận trong Python

Cho ma trận các phần tử duy nhất và số sum. Tìm tất cả cặp (x,y) với x,y từ 2 hàng khác nhau sao cho x + y = sum.

Ví dụ: ma trận 4x4, sum=13 → [(2,11), (4,9), (3,10), (5,8), (12,1)].

Giải thuật

• Sắp xếp từng hàng.
• Với mỗi cặp hàng (i,j) với i
• Thu thập tất cả cặp tìm được.

Ví dụ

def sum_pair(matrix, target_sum):
    res = []
    n = len(matrix)
    for row in matrix:
        row.sort()
    for i in range(n - 1):
        for j in range(i + 1, n):
            low, high = 0, n - 1
            while low < n and high >= 0:
                s = matrix[i][low] + matrix[j][high]
                if s == target_sum:
                    res.append((matrix[i][low], matrix[j][high]))
                    low += 1
                    high -= 1
                elif s < target_sum:
                    low += 1
                else:
                    high -= 1
    return res

matrix = [
    [2, 4, 3, 5],
    [6, 9, 8, 7],
    [10, 11, 14, 12],
    [13, 1, 15, 16]
]
print(sum_pair(matrix, 13))

Đầu vào

[[2,4,3,5],[6,9,8,7],[10,11,14,12],[13,1,15,16]], sum=13

Đầu ra

[(4, 9), (5, 8), (2, 11), (3, 10), (12, 1)]