Recursion Quiz - Couldn't Solve

Question

Today my CPSC professor assigned a quiz in python, the topic was recursion.

The whole class got stuck on question number two, which is below. Nobody was able to even come close to a solution.

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

Example code:

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]]

---

You are only allowed to modify the underscores, such as my example below may demonstrate.

My solution was so far from close, it really shouldn't even be considered:

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]]

Does anyone know how this could be solved? It seems like quite a challenging problem when we have only 15 minutes to solve it.

Just for reference, he said he would drop the question considering nobody in the class - advanced comp sci class of about 10 carefully selected students - could solve it.

Answer 1

I think there's a bug in the question. The base case for the recursion is wrong.

The set of all subsets of an empty set is not the empty set, but rather, the set containing the empty set.

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

should be

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

Added: With that patch, here's a solution:

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

Answer 2

I don't believe this is solvable without some major hackery, because the base case is wrong. For [], there should be one subset: [] itself. But return A returns no subsets.

So, instead of just doing A[:1] + L, you need to do [A[:1] + L]. And, instead of A[:1] + X + result, you have to do [A[:1]] + X + result. So:

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

This still leaves the empty list out of the subsets for anything. And the only way to fix that is something stupid like this:

    return ([] if [] in X + result else [[]]) + [A[:1]] + X + result

This will at least return the right values… but in the wrong order, and with duplicates of all one-element subsets. You can extend the hackiness further if you want; I don't think it's worth it.

Answer 3

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

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]]