Generating Power Set with Recursion and Yield Statement in Python

Question

I am a bit new to Python and am working through programming exercises. I have written the following recursive method to generate the power set based on an input list in Python. It should return a generator that generates the power set of a given list passed in as s. Each element in the power set should be a set.

def gps(s, res=set()):
    if s:
        elem = s.pop()
        gps(s, res)
        res.add(elem)
        gps(s, res)
    else:
        yield res

When I call it using list(gps([1,2])) however it gives me []. The correct result should be something like [set(), {1}, {2}, {1, 2}].

I removed the yield statement, added two lines of code and played around with print statements to get this code, which prints the right results and seems like a step closer:

def gps(s, res=set()):
    if s:
        elem = s.pop()
        gps(s, res)
        res.add(elem)
        gps(s, res)
        s.append(elem)
        res.remove(elem)
    else:
        print(res)

After reading another Stack Overflow answer I modified my function to use yield from but the modified code below still gives me incorrect results:

def gps(s, res=set()):
    if s:
        elem = s.pop()
        yield from gps(s, res)
        res.add(elem)
        yield from gps(s, res)
        s.append(elem)
        res.remove(elem)
    else:
        yield res

    

Where am I going wrong with my approach? Any tips and clarifications would be appreciated.

Answer 1

Maybe you could try this code, without any built-in methods.

def subset(nums):
    ans = [[]]

    for n in nums:
        ans += [a+[n] for a in ans]

    return ans


nums = [1, 2, 3]

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

Or you still prefer the generator version:

def powerset(nums):
    """
    This is a generator version
    """
    if len(nums) <= 1:
        yield nums
        yield []
    else:
        for x in powerset(nums[1:]):
            yield [nums[0]]+ x
            yield x



if __name__ == '__main__':
    nums = [1, 2, 3]
    print(list(powerset(nums)))