二维数组特定和查找问题：Python算法调试求助

问题背景 #

给定二维数组，需判断是否存在满足以下条件的元素子集：

• 元素总和等于目标值
• 子集内任意两个元素不同行不同列

示例数组：

T=[[1,2,3,4], [5,6,7,8], [9,5,6,7], [2,4,6,8]]

• 目标和26时，T[0][1]+T[1][2]+T[2][0]+T[3][3]=2+7+9+8=26，应返回True
• 目标和20时，T[0][0]+T[1][3]+T[2][1]+T[3][2]=20，应返回True

用户编写的递归函数如下：

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)

测试发现：

• 目标和21时（T[0][0]+T[1][1]+T[2][2]+T[3][3]=21）函数返回True
• 目标和26时却返回False，需排查问题。

问题根源 #

你的函数存在两个致命问题：

1. 循环提前终止：在for循环中，第一次递归调用就直接return，导致程序只会尝试当前行的第一个可用列，不会遍历其他可能的列选项。比如目标和26的场景，第一行第一个列值为1，这条分支的最终和无法达到26，但函数不会尝试第一行的第二个列（值为2）就直接返回了。
2. 可变默认参数陷阱：columns=set()作为默认参数，会在函数定义时初始化一次，后续所有调用都会复用同一个集合，导致不同递归分支的列选择状态互相干扰，出现错误的回溯结果。

修正后的代码 #

def given_sum(T, target_sum, row=-1, current_sum=0, columns=None):
    # 每次调用初始化columns，避免可变默认参数的复用问题
    if columns is None:
        columns = set()
    
    if target_sum == current_sum:
        return True
    if current_sum > target_sum:
        return False
    # 处理完所有行后，直接校验当前和是否匹配目标值
    if row >= len(T)-1:
        return current_sum == target_sum
    
    row += 1
    # 遍历当前行的所有列，适配非方阵情况
    for col in range(len(T[row])):
        if col in columns:
            continue
        columns.add(col)
        # 递归调用，仅当找到有效路径时才返回True
        if given_sum(T, target_sum, row, current_sum + T[row][col], columns):
            return True
        # 回溯：移除当前列，尝试当前行的下一个列选项
        columns.remove(col)
    # 当前行所有列都尝试后仍无有效路径，返回False
    return False

测试验证 #

用示例数组测试：

T = [[1,2,3,4], [5,6,7,8], [9,5,6,7], [2,4,6,8]]
print(given_sum(T, 26))  # 输出True
print(given_sum(T, 20))  # 输出True
print(given_sum(T, 21))  # 输出True

内容的提问来源于stack exchange，提问作者Stiffo