使用递归回溯生成集合的所有子集 (Python)

Question

我试图理解回溯，但我被困在这个问题上，这里是提示：

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

示例输入：[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

当我 return res 时，我得到一个大小为 2^(len(nums)) 的空列表列表，这是正确的大小，但没有数字。但是，在我执行 res.append(temp) 之前打印 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

变量是对实际值的引用。但是，由于 Python 列表是可变的，当您通过一个引用更改值时，另一个引用也会反映更改。

>>> a = [1, 3]
>>> b = a
>>> b
[1, 3]
>>> b.append(1)
>>> b
[1, 3, 1]
>>> a
[1, 3, 1]

在将列表附加到修复之前复制列表。

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

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

如其他答案所述，您也可以使用 res.append(temp[:])。

Answer 2

您将对同一列表对象的多个引用附加到 res。我们可以通过做

来证明这一点

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

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

因此，您对 temp 所做的各种更改得到 "lost"，而 res 的最终内容将是对 temp 最终值的 8 个引用是，在本例中它是空列表。

解决此问题的简单方法是将 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 开始。

在每个循环中，我们通过遍历 z 并使 w 中的每个项目成为 z 中相应项目的副本来创建一个新列表 w当前 x 附加到它。然后我们用 w 的内容扩展 z。

只是为了好玩，这是一个迭代生成器，它从位串中生成子集（以自然顺序）。这种方法实际上是非常有效的，如果你想要一个大序列的所有子集而不消耗大量 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]

使用递归回溯生成集合的所有子集 (Python)

Generating All Subsets of a Set Using Recursive Backtracking (Python)

python

recursion

permutation

backtracking

recursive-backtracking