Przeszukiwanie z nawrotami

Mam problem z rozwiązaniem tego zadania:
Wejście: n, s – dodatnie liczby naturalne
a – tablica dwuwymiarowa, elementy a[i][j] są dodatnie dla każdych 0≤i, j≤n – 1
Wyjście:
− 1 – gdy s można uzyskać jako sumę n liczb uzyskanych przez wybranie po jednej liczbie z
każdej kolumny tablicy a
− 0 – w przeciwnym przypadku

Mój kod:

 while k < n and k >= 0:
    for i in range(n):
        if (Suma - tab[k][i]) >= 0:
            Suma -= tab[k][i]
            k += 1
            break
    else:
        k -= 1

if Suma == 0:
    print("1")
else:
    print("0")

Ale mam problem bo jak pojawiają się same małe elementy, których suma jest mniejsza od tej liczby to nie wiem jak wybierać te większe liczby.

Moim zdaniem to powinna być funkcja posiadająca w swoim ciele pojedynczą petlę w której wybierze jeden z wierszy pierwszej kolumny i przejdzie(rekursywnie) do wyboru liczby z kolejnej kolumny i tak....do ostatniej kolumny.
Poczytaj o problemie ośmiu hetmanów, sudoku.

Ale iteracyjnie też da się to zrobić. Jak chcesz możesz pokazać jak powinno to wyglądać rekurencyjnie.