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

I have made two implementations of a backtracking algorithm to solve this challenge on Codewars ( https://www.codewars.com/kata/5a6b24d4e626c59d5b000066 ) . My problem is that I grasp why the first implementation works but not why the second one . I think that my problem is in the return statement in the last line with the hash signs . I don't get why when the backtracking is finishing because a solution is found the second implementation returns the right solution instead of an empty list , is it because when the solution is passed to the previous call of the function his value in the previous call ( which was with an element fewer ) is overwritten with the complete solution ?

首先:

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)
评论
  • 宇智波~
    宇智波~ 回复

    It works because they return the same, both solutions return sol. It's just that the second one returns the variable sol directly, whereas the first one returns the output of the function (which is the same variable sol passed as argument).