使用递归回溯（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`时，我得到一个大小为`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)

- YSA

Answer 1

您正在将多个相同列表对象的引用附加到 res 中。我们可以通过执行以下操作来演示这一点。

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

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

因此，您对temp所做的各种更改会“丢失”，并且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中相应项目的副本并添加当前x来创建一个新列表w。然后将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]

- PM 2Ring

---

我明白你的意思。有没有更优雅/Pythonic的做法？切片是否昂贵？我想知道最好的方法是什么。感谢你的解释！ - YSA

@YSA：切片执行的额外工作是必须完成的工作。 - user2357112

@YSA 你也可以使用copy模块和copy.copy(temp) - Oliver Ni

@PM 2Ring，您能否解释一下迭代解决方案，我对它感到困惑。递归的解释很完美。 - YSA

@YSA 这有帮助吗？ - PM 2Ring

@PM 2Ring 谢谢！请继续传播智慧！ - YSA

Answer 2

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

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

在将其附加到fix之前，先复制该列表。

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[:])。

- Oliver Ni

---

列表与其他对象没有区别对待。 - user2357112

b.append(1) 所做的更改能够通过 a 看到并不意味着列表会得到任何特殊处理。您可能想要阅读一下关于 Python 变量和赋值工作方式 的内容。 - user2357112

@OliverNi 您的答案是正确的，因为它产生了正确的输出，但您复制的方式有些奇怪。然后，您的解释有点粗糙，关于数组如何与“普通”变量“不同”。在某种程度上，我同意您的看法，但它们实际上像任何其他对象一样被处理，具有可变字段。 - JohanL

@JohanL 好的，我会编辑我的答案，使其更加清晰。 - Oliver Ni

@user2357112 这样好一些吗？ - Oliver Ni

是的，这样更好。 - user2357112