递归测验 - 无法解决

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名精心挑选的学生的高级综合科学课程 - 可以解决它,他会放弃这个问题.

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