回溯解决方案中的变量值不会回到其原始状态

Question

我试图构建一个解决方案来解决生成长度为 n

的 k 所有可能组合的问题

例如：k = 4，n = 2

输出：

[1, 1]
[1, 2]
[1, 3]
[1, 4]
[2, 1]
[2, 2]
[2, 3]
[2, 4]
[3, 1]
[3, 2]
[3, 3]
[3, 4]
[4, 1]
[4, 2]
[4, 3]
[4, 4]

这是我实现的逻辑的伪代码

def backTrack(arr):
    if length(arr) == k:
        return

    loop through from 1 to n <- for i in range(1, n+1):
        i = value of loop
        add i to an array variable arr <- arr.append(i)
        backtrack(arr) <- recurse
        remove last index value from arr <- arr = arr[:-1]

对于上面的代码，我应该得到以下值

on depth 1:
   the loop starts with 1
   and arr = [1]
   
   then it recuses to depth 2
      the loop starts with 1
       and arr = [1, 1]
       since the length of arr = k =2 it wont recurse further and continue
       arr = arr[:-1] = arr = [1]

       then i will be 2 
       and arr = [1,2]
       similarly [1, 3] and [1, 4] and then it goes to depth 1 or the parent call

on depth 1
  value of i = 1
   and arr  = 1
   now, arr = arr[:-1] that makes arr = []
  and now i becomes 2 and the process continues

但是调试用下面的伪代码编写的代码，表明在深度 1 上 arr 永远不会变回 [1] 而是变成 [1, 1] 我仍然在努力理解为什么会这样。

下面是带有打印语句的调试解决方案

class Solution(object):
    def combine(self, n, k):
    
        def backTrack(arr, result, depth):
            if len(arr) == k:
                return
    
            for i in range(1, n + 1):
                arr.append(i)
                print("depth = " + str(depth) + ", i = " + str(i) + ", arr=" + str(arr))
                backTrack(arr, result, depth + 1)
            
                print("depth -> " + str(depth) + ", i-> " + str(i) + ", arr-> " + str(arr))
                arr = arr[:-1]

        
        return backTrack([], [], 1)



ob = Solution()
result = ob.combine(4, 2)

下面是调试输出

depth = 1, i = 1, arr=[1]
depth = 2, i = 1, arr=[1, 1]
depth -> 2, i-> 1, arr-> [1, 1]
depth = 2, i = 2, arr=[1, 2]
depth -> 2, i-> 2, arr-> [1, 2]
depth = 2, i = 3, arr=[1, 3]
depth -> 2, i-> 3, arr-> [1, 3]
depth = 2, i = 4, arr=[1, 4]
depth -> 2, i-> 4, arr-> [1, 4]
depth -> 1, i-> 1, arr-> [1, 1] * going back to parent call arr never becomes 1
depth = 1, i = 2, arr=[1, 2]
depth -> 1, i-> 2, arr-> [1, 2]
depth = 1, i = 3, arr=[1, 3]
depth -> 1, i-> 3, arr-> [1, 3]
depth = 1, i = 4, arr=[1, 4]
depth -> 1, i-> 4, arr-> [1, 4]

我在 * 中标记了调试器输出，以显示父调用中的 arr 状态永远不会恢复到 1

我想明白为什么会这样。

Answer 1

根据您的伪代码，实现应该是这样的：

class Solution(object):
    def combine(self, n, k):
        total = []

        def backTrack(depth, stack):
            if depth >= k:
                total.append(stack[:])
                return

            for i in range(1, n + 1):
                stack.append(i)
                backTrack(depth + 1, stack)
                stack.pop()

        backTrack(0, [])
        return total

在您的实现中，这行代码 arr = arr[:-1] 不会从列表中删除任何内容。事实上，它通过使整个列表与最后一个元素相等来阻止整个列表。

Answer 2

arr = arr[:-1] 创建 arr 的 新副本 ，删除最后一个元素并将其分配给局部变量 arr。这意味着递归调用的其他范围内的 arrs 引用了一些其他仍然有最后一个元素的列表。

您需要通过编写 arr.pop().

从该列表中删除最后一个元素

如果您需要进一步解释 python 中的可变和不可变以及为什么它以这种方式工作，请发表评论。

回溯解决方案中的变量值不会回到其原始状态

variable value in a backtracking solution is not going back to its original state

python

algorithm

backtracking