Find specific sum in a 2D array - python algorithms

Question

We are given a 2D array and asked to write a fuction that will search the array for a specific subset of elements that sum up to the given target sum and return True, if it finds the subset and False otherwise. The specificity of this subset is the condition that any two of the elements must not be taken from the same column or row of the 2D array. For example, for an array: T=[[1,2,3,4], [5,6,7,8], [9,5,6,7], [2,4,6,8]] and target sum: target_sum = 26 the output should be True, because T[0][1]+T[1][2]+T[2][0]+T[3][3] == 2+7+9+8 == 26, The same for the same array and target_sum = 20, because T[0][0]+T[1][3]+T[2][1]+T[3][2]==20

This is what I tried:

def given_sum(T, target_sum, row=-1, current_sum=0, columns=set()):

    if target_sum==current_sum:
        return True
    if current_sum>target_sum:
        return False
    if row>=len(T)-1:
        return False
    row+=1
    for col in range(len(T)):
        if col in columns:
            continue
        columns.add(col)
        return given_sum(T, target_sum, row, current_sum+T[row][col],columns)
        columns.remove(col)

For the example array as above: T=[[1,2,3,4], [5,6,7,8], [9,5,6,7], [2,4,6,8]] and target_sum = 21, it prints True, because T[0][0]+T[1][1]+T[2][2]+T[3][3]==21, but for target_sum = 26, it prints False despite the fact that T[0][1]+T[1][2]+T[2][0]+T[3][3]==26 Please help!

Here are some questions need to be clarified - is the answer always ```unique```? In the example, ```1+8+9+8``` also satisfied (26). — Daniel Hao, Dec 18 '22 at 14:01
Just return True if such a subset exists and False if it doesn't exist - no, the answer doesn't need to be unique — Stiffo, Dec 18 '22 at 14:50
If you squint your eyes, you will see that the exploration of the solutions of the problem is tree-shaped. So a recursive implementation seems possible, but not necessarily easy. What is your problem ? "why does my code produces the wrong output" ? Why did you return False for 26, and True for 21 ? That is a debugging question. [What is a debugger and how can it help me ?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). Currently your question looks like "fix my code please". — Lenormju, Dec 19 '22 at 12:43

score 0 · Answer 1 · answered Dec 19 '22 at 12:52

Just putting your code in my IDE tells me that :

your columns.remove call is unreachable (being after a return statement)
your columns function parameter is mutable, this looks like a footgun ! see Why does PyCharm warn about mutable default arguments? How can I work around them?

Then adding given_sum(T=[[1,2,3,4], [5,6,7,8], [9,5,6,7], [2,4,6,8]], target_sum=26), putting three debug points (one on each return True or False, which are your terminal cases), and I get :

row >= len(T) - 1 eveluates to True, so it bubbles up that False.

No sum was really checked, so I think your algorithm is wrong.
A debugger can get you there very fast.

Find specific sum in a 2D array - python algorithms

1 Answers1