我在Python中的递归解决方案是用当前lis附加和替换应答列表中的所有当前项

Question

我试图实现一个Python解决方案来解决编程问题 寻找整数数组中的所有子集。我应该返回一个数组 它包含整数数组的所有子集，并且没有重复项 已排序。你知道吗

def subsetHelper(cur_set, index, A, ans):
    if index >= len(A):
        print "appending ", cur_set
        ans.append(cur_set)
        print "ans: ", ans
        return
    # don't include current number
    subsetHelper(cur_set, index+1, A, ans)

    # include current number
    cur_set.append(A[index])
    subsetHelper(cur_set, index+1, A, ans)
    cur_set.pop()

def subsets(A):
    A.sort()
    ans = []
    cur_set = []
    # dont include current number
    subsetHelper(cur_set, 0, A, ans)
    return ans

在C++中实现这一逻辑会得到正确的返回值。然而，当我在Python中这样做的时候，我得到的只是最后一个空列表的集合，而在迭代过程中，它将相同的当前列表复制到列表中的所有项，即使打印输出每次都显示它附加了正确的子集。为什么会这样？以下是输出：

print subsets([1,2,3])
appending  []
ans:  [[]]
appending  [3]
ans:  [[3], [3]]
appending  [2]
ans:  [[2], [2], [2]]
appending  [2, 3]
ans:  [[2, 3], [2, 3], [2, 3], [2, 3]]
appending  [1]
ans:  [[1], [1], [1], [1], [1]]
appending  [1, 3]
ans:  [[1, 3], [1, 3], [1, 3], [1, 3], [1, 3], [1, 3]]
appending  [1, 2]
ans:  [[1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2]]
appending  [1, 2, 3]
ans:  [[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]
[[], [], [], [], [], [], [], []]

Answer 1

问题是在调用之间使用cur\u set list对象，因此即使在cur_set被添加到ans之后，对susetHelper的未来调用仍然会修改列表，特别是对cur_set.pop()的未来调用会清空列表。您可以通过存储cur_set的副本而不是确切的对象来解决这个问题。你知道吗

def subsetHelper(cur_set, index, A, ans):
    if index >= len(A):
        print "appending ", cur_set
        ans.append(cur_set[:])
        print "ans: ", ans
        return
    # don't include current number
    subsetHelper(cur_set, index+1, A, ans)

    # include current number
    cur_set.append(A[index])
    subsetHelper(cur_set, index+1, A, ans)
    cur_set.pop()

def subsets(A):
    A.sort()
    ans = []
    cur_set = []
    # dont include current number
    subsetHelper(cur_set, 0, A, ans)
    return ans

print subsets([12, 13])

并不是说你在这里混合了基于状态的oop和函数式编程风格。这在原则上没有错，但是调试基于状态的递归可能非常令人沮丧。如果这是一个学习练习，我建议您首先尝试以纯函数的方式（递归方式）解决这个问题，然后以纯基于状态的方式再次进行。两种方法都能让你更好地理解这个问题。你知道吗

Answer 2

这里有两个问题：第一个问题是你ans.extend而不是ans.append，一旦改变，我们得到了第二个问题，即结尾处的空列表，原因是append只在列表ans中添加一个对cur_set的引用，这个引用在递归过程中删除了所有元素，所以最后会有多个对结尾处为空的同一个列表的引用，要解决这个问题，您只需要在列表的当前内容中添加一个副本，例如list(cur_set)。你知道吗

也没有理由让这成为一门课

def subsetHelper(cur_set, index, A, ans):
    if index >= len(A):
        print "appending ", cur_set
        ans.append(list(cur_set))  # < - here was the problem
        print "ans: ", ans
        return
    # don't include current number
    subsetHelper(cur_set, index+1, A, ans)

    # include current number
    cur_set.append(A[index])
    self.subsetHelper(cur_set, index+1, A, ans)
    cur_set.pop()

def subsets(A):
    A.sort()
    ans = []
    cur_set = []
    # dont include current number
    subsetHelper(cur_set, 0, A, ans)
    return ans

试验

>>> subsets([1,2,3])
appending  []
ans:  [[]]
appending  [3]
ans:  [[], [3]]
appending  [2]
ans:  [[], [3], [2]]
appending  [2, 3]
ans:  [[], [3], [2], [2, 3]]
appending  [1]
ans:  [[], [3], [2], [2, 3], [1]]
appending  [1, 3]
ans:  [[], [3], [2], [2, 3], [1], [1, 3]]
appending  [1, 2]
ans:  [[], [3], [2], [2, 3], [1], [1, 3], [1, 2]]
appending  [1, 2, 3]
ans:  [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
>>>