在二维数组中找到特定的和- python算法

Question

给定一个2D数组，并要求编写一个函数，该函数将在数组中搜索与给定目标和之和相同的特定元素子集，如果找到该子集则返回True，否则返回False。这个子集的特殊性是一个条件，即任何两个元素不能取自2D数组的同一列或行。例如，对于数组:T=[[1,2,3,4], [5,6,7,8], [9,5,6,7], [2,4,6,8]]目标和:target_sum = 26输出应该是真的,因为T [0] [1] + T [1] [2] + T [2] [0] + T[3][3] = = 2 + 7 + 9 + 8 = = 26日对于相同的数组和target_sum =20也是一样的，因为T[0][0]+T[1][3]+T[2][1]+T[3][2]==20

这是我尝试过的:

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)

对于上面的示例数组:T=[[1,2,3,4], [5,6,7,8], [9,5,6,7], [2,4,6,8]]它打印和target_sum = 21日真的,因为T [0] [0] + T [1] [1] + T [2] [2] + T[3][3] = = 21日但是对于target_sum =26，它打印False，尽管T[0][1]+T[1][2]+T[2][0]+T[3][3]==26请帮助!

Answer 1

只要把你的代码放在我的IDE告诉我:

• 您的columns.remove呼叫不可达(在return语句之后)
• 你的columns函数参数是可变的这看起来像个步兵枪!参见为什么PyCharm对可变的默认参数发出警告?我该如何绕开他们?

然后添加given_sum(T=[[1,2,3,4], [5,6,7,8], [9,5,6,7], [2,4,6,8]], target_sum=26)，放置三个调试点(每个return True或False上一个，这是您的终端案例)，我得到:

row >= len(T) - 1被计算为True，所以它会冒泡到False。

没有真正检查和，所以我认为你的算法是错误的。
调试器可以让你很快到达那里。