Теория
Задача решается полным перебором всех комбинаций. Быстрее нельзя, и вот почему:
Заменим задачу на более простую: для данного набора списков требуется ответить есть ли комбинация с нулевой разницей или её нет. Ясно что если вы умеете решать общую задачу (про поиск минимальной разницы), то и эту решите без труда.
Рассмотрим списки из двух элементов. Например:
[0, 5]
[4, 0]
[8, 0]
[1, 0]
Заметим что если ко всем элементам конкретного списка прибавить одно и то же число, ответ останется прежним. Добавим к каждому списку такое число, чтобы первый элемент стал нулем:
[0, 5]
[0, -4]
[0, -8]
[0, -1]
Комбинация с нулевой разницей тогда возможна только если есть комбинация вторых чисел списков, которая даёт нулевую сумму. Можно среди этих чисел отыскать непустую комбинацию с нулевой суммой?
5, -4, -8, -1
Это задача о сумме подмножеств:
Задача заключается в нахождении (хотя бы одного) непустого
подмножества некоторого набора чисел, чтобы сумма чисел этого
подмножества равнялась нулю.
Она NP-полная. То есть, она решается только полным перебором вариантов.
Раскручиваем цепочку назад. Если бы для исходной задачи существовало бы быстрое решение, то и задача проверки нулевой разницы для списков из двух элементов решалась бы быстро. Тогда и задача о сумме подмножеств решалась бы быстро. А это, скорее всего, невозможно - NP-полнота.
Ещё раз, коротко: задача может быть решена только полным перебором всех комбинаций.
Практика
Перебор написать не сложно:
def cost(s):
return max(s) - min(s), -sum(s)
def search(a):
m = len(a)
n = len(a[0])
s = [0] * n
best_s = a[0]
best_c = cost(a[0])
def rec(i, empty):
nonlocal best_s
nonlocal best_c
if i == m:
if not empty:
c = cost(s)
if c < best_c:
best_s = s[:]
best_c = c
else:
rec(i + 1, empty)
for j in range(n):
s[j] += a[i][j]
rec(i + 1, False)
for j in range(n):
s[j] -= a[i][j]
rec(0, True)
return best_s
def main():
s = search([
[1, 3, 0],
[2, 1, 4]
])
print(s, cost(s))
s = search([
[0, 0, 5],
[0, 4, 0],
[0, 8, 0],
[2, 1, 0],
[3, 0, 0]
])
print(s, cost(s))
main()
$ python temp.py
[3, 4, 4] (1, -11)
[5, 5, 5] (0, -15)