为什么这两种回溯算法具有相同的输出?

Question

我已经做了两个回溯算法的实现来解决Codewars(https://www.codewars.com/kata/5a6b24d4e626c59d5b000066(上的这个挑战。我的问题是我掌握了为什么第一个实现有效，但不了解为什么第二个实现。我认为我的问题出在最后一行带有哈希符号的返回语句中。我不明白为什么回溯终止，因为找到了解决方案，第二个实现返回正确的解决方案而不是空列表。是因为当解决方案被传递给函数的上一个调用时，他在上一个调用中的值(元素更少(被完整的解决方案覆盖了吗？

第一：

def square_sums_row(n):
a , sol = [ x for x in range(1,n+1)] , []
def recurse(a,sol):
if a == [] : 
return sol 
for i,x in enumerate(a) :
if is_valid(x,sol) :
sol.append(x)
iterate = recurse(a[:i]+a[i+1:],sol) ###########
if iterate : ###########
return iterate #########
sol.pop(-1)
return False
def is_valid(x,sol):
if len(sol) == 0 :
return True
if (( sol[-1] + x )**0.5) % 1 == 0:
return True
return False
return recurse(a,sol)

第二：

def square_sums_row(n):
s , sol = [ x for x in range(1,n+1)] , []
def recurse(s,sol):
if s == [] :  
return sol
for i,x in enumerate(s) :
if is_valid(x,sol) :
sol.append(x)
if recurse(s[:i]+s[i+1:],sol) : ###########
return sol ##############
sol.pop(-1)
return False
def is_valid(x,sol):
if len(sol) == 0 :
return True
if (( sol[-1] + x )**0.5) % 1 == 0:
return True
return False
return recurse(s,sol)

Answer 1

为了扩展另一个答案，只有一个列表对象sol被传递和返回。它永远不会被复制。这是强调这一点的另一种解决方案。这里sol不是任何地方的参数，它只是从闭包中获取的，内部函数只返回

布尔值。

def square_sums_row(n):
sol = []
def recurse(s):
if s == []:
return True
for i, x in enumerate(s):
if is_valid(x):
sol.append(x)
iterate = recurse(s[:i] + s[i + 1:])  ###########
if iterate:  ###########
return True
sol.pop(-1)
return False
def is_valid(x):
if len(sol) == 0:
return True
if ((sol[-1] + x) ** 0.5) % 1 == 0:
return True
return False
if recurse([x for x in range(1, n + 1)]):
return sol
else:
return False

Answer 2

它之所以有效，是因为它们返回相同的，两种解决方案都返回sol.只是第二个直接返回变量sol，而第一个返回函数的输出(sol作为参数传递的相同变量(。