python - 递归测验 - 无法解决

Question

今天我的 CPSC 教授布置了一个 python 测验，主题是递归。

全类都被下面的第二个问题卡住了。没有人能够接近解决方案。

def sub_set(A):
    if A == []: return A
    X = sub_set(A[1:])
    result = []
    for L in X:
        result += _____
    return _____

示例代码:

print(sub_set([1, 2]))    # [[], [1], [2], [1, 2]]
print(sub_set([1, 2, 3])) # [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

---

您只能修改下划线，如下面的示例所示。

我的解决方案还差得远，真的不应该考虑:

def sub_set(A):
    if A == []: return A
    X = sub_set(A[1:])
    result = []
    for L in X:
        result += _____
    return result + [A[:1]] + [A] + [A[::2]]

#sub_set([1, 2, 3]) -> [[3], [3], [3], [2], [2, 3], [2], [1], [1, 2, 3], [1, 3]]

有人知道怎么解决吗？当我们只有 15 分钟的时间来解决它时，这似乎是一个相当具有挑战性的问题。

仅供引用，他说考虑到类没有人会放弃这个问题——大约 10 名精心挑选的学生组成的高级 comp sci 类——可以解决这个问题。

Answer 1

我认为问题中存在错误。递归的基本情况是错误的。

空集的所有子集的集合不是空集，而是包含空集的集合。

def sub_set(A):
    if A == []: return A

应该是

def sub_set(A):
    if A == []: return [A]

添加:有了那个补丁，这里有一个解决方案:

def sub_set(A):
    if A == []: return [A]
    X = sub_set(A[1:])
    result = []
    for L in X:
        result += [L, A[0:1] + L]
    return result