使用递归回溯（Python）生成集合的所有子集

Question

我试图了解回溯，但是我陷入了这个问题，这是提示：

给定一组不同的整数，返回所有可能的子集。

输入示例： [1,2,3]

输出示例： [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

这是我的代码：

def subsets(nums):
    res = []
    backtrack(res, [], nums, 0)
    return res

def backtrack(res, temp, nums, start):
    # print(temp)
    res.append(temp)
    for i in range(start, len(nums)):
        temp.append(nums[i])
        backtrack(res, temp, nums, i + 1)
        temp.pop() # Backtrack

当我返回时，res我得到一个空列表size的列表2^(len(nums))，该列表是正确的大小，但是数字不存在。但是，temp在执行此操作之前res.append(temp)，打印表明temp进行了正确的输出。

例如

res = [[], [], [], [], [], [], [], []]

打印报表：

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

为什么所做的更改没有保留到res列表中？

编辑1：

此解决方案有效，有什么区别？

def subsets(nums):
    res = []
    backtrack(res, [], nums, 0)
    return res

def backtrack(res, temp, nums, start):
    # print(temp)
    res.append(temp)
    for i in range(start, len(nums)):
        backtrack(res, temp + [nums[i]], nums, i + 1)

Answer 1

您要将多个引用附加到的同一列表对象res。我们可以通过这样做来证明这一点

result = subsets([1, 2, 3])
print([id(u) for u in result])

这将打印8个相同ID的列表。

因此，您为temp获得“丢失”而进行的各种更改以及的最终内容res将是对8的最终值的引用temp，在本例中为空列表。

解决此问题的简单方法是将的副本附加temp到res。

def subsets(nums):
    res = []
    backtrack(res, [], nums, 0)
    return res

def backtrack(res, temp, nums, start):
    res.append(temp[:])
    for i in range(start, len(nums)):
        temp.append(nums[i])
        backtrack(res, temp, nums, i + 1)
        temp.pop() # Backtrack

print(subsets([1, 2, 3]))

输出

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

FWIW，我意识到本练习的重点是练习递归，但是在Python中，除非您确实需要递归，否则最好避免递归（例如，处理树之类的递归数据结构）。但这是一个更紧凑的迭代解决方案。

def subsets(seq):
    z = [[]]
    for x in seq:
        z += [y + [x] for y in z]
    return z

要查看其工作原理，我们可以将其扩展一点，然后添加一个print呼叫。

def subsets(seq):
    z = [[]]
    for x in seq:
        print('z =', z, 'x =', x)
        w = []
        for y in z:
            w += [y + [x]]
        z += w
    return z

result = subsets([1, 2, 3])
print(result)  

输出

z = [[]] x = 1
z = [[], [1]] x = 2
z = [[], [1], [2], [1, 2]] x = 3
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

我们从z包含一个空列表的列表开始。

在每个循环中，我们w通过循环z并将每个项目w复制到相应项目的副本中z并x附加当前内容来创建新列表。然后z，我们扩展的内容w。

只是为了好玩，这里有一个迭代生成器，它从位串生成子集（以自然顺序）。这种方法实际上是相当有效的，如果您希望一个大序列的所有子集而不消耗大量RAM，那将是一个很好的选择。

def subsets(seq):
    w = len(seq)
    for i in range(1<<w):
        yield [u for u, v in zip(seq, reversed('{:0{}b}'.format(i, w))) if v=='1']

print(*subsets([1, 2, 3]))

输出

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