Understanding recursion using power set example

Question

I have written a simple piece of code to print all subsets of a set using recursion. I have a hard time understanding the output. For example, the first line in the output shows an empty set and a singleton of 3 whereas I was expecting an empty set and singleton of 1 to be printed followed by an empty set, singleton of 1, singleton of 2 etc. However, that is not what gets printed. I do not know how to visualize recursion tree. Are there any general techniques to accomplish the visualisation? I tried drawing a tree but it quickly gets confusing.

def subsets(self, nums):
        inp = nums
        out = []
        result=[]
        def helper(inp,out,index):
            if index==len(inp):
                result.append(out)
                return
            helper(inp,out,index+1)
            helper(inp,out+[inp[index]],index+1)
            print(result)
        helper(inp,out,0)
        return result

The output from the print statement for the input '[1,2,3]' is shown below

[[], [3]]
[[], [3], [2], [2, 3]]
[[], [3], [2], [2, 3]]
[[], [3], [2], [2, 3], [1], [1, 3]]
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

It would be helpful if you also included the input that led to your included output. — shn, Dec 10 '20 at 21:47
change where you print to the beginning of your function for example and/or add extra prints — Copperfield, Dec 10 '20 at 21:49
Does this answer your question? [Python recursive function to display all subsets of given set](https://stackoverflow.com/questions/26332412/python-recursive-function-to-display-all-subsets-of-given-set) — PM 77-1, Dec 10 '20 at 21:49
Stepping through the program with a debugger should solve this problem fairly fast — , Dec 10 '20 at 22:05

Thomas Mailund · Accepted Answer · 2020-12-18T03:22:43.793

If you add an "indentation" parameter to your function, while you explore it, you can immediately see which function calls which:

def subsets(nums):
        inp = nums
        out = []
        result=[]
        def helper(indent,inp,out,index):
            print(f"{indent}->helper({inp},{out},{index})")
            if index==len(inp):
                result.append(out)
                return
            helper(indent+'--',inp,out,index+1)
            helper(indent+'--',inp,out+[inp[index]],index+1)
        helper('',inp,out,0)
        return result

The result will look like:

->helper([1, 2, 3],[],0)
--->helper([1, 2, 3],[],1)
----->helper([1, 2, 3],[],2)
------->helper([1, 2, 3],[],3)
------->helper([1, 2, 3],[3],3)
----->helper([1, 2, 3],[2],2)
------->helper([1, 2, 3],[2],3)
------->helper([1, 2, 3],[2, 3],3)
--->helper([1, 2, 3],[1],1)
----->helper([1, 2, 3],[1],2)
------->helper([1, 2, 3],[1],3)
------->helper([1, 2, 3],[1, 3],3)
----->helper([1, 2, 3],[1, 2],2)
------->helper([1, 2, 3],[1, 2],3)
------->helper([1, 2, 3],[1, 2, 3],3)

So you can immidiately see why you get [] first--you get it when you go all the way through the list without including anything in the results. You get [3] next because you backtrack to the call where you add 3 and then go to the end. You get [2] by backtracking a bit further, to where you include 2 in the output, and then down the path that doesn't add 3. Then you get [2,3] because you backtrack one level up, to the call that has 2 included in the result, and this time go to the path that adds 3.

It probably isn't the easiest way to compute a power-set, though. There is a one-to-one correspondence between the powerset of size n and the binary numbers between 0 and 2**n-1. For each number, the 1-bits indicate which elements to include in the set. So you can also compute the powerset like this:

def subsets(nums):
    return [
        [nums[j] for j, b in enumerate(reversed(format(i, 'b'))) if b == '1']
        for i in range(2**len(nums))
    ]

It runs in exponential size, but so does the recursive version, and that is unavoidable when the output is exponential in the size of the input.

Wow, this is super helpful. Thanks a ton! – ForumWhiner Dec 11 '20 at 13:45 — ForumWhiner, Dec 11 '20 at 13:45

Understanding recursion using power set example

1 Answers1