subsets recursion question

first lets discuss how many subsets can be made.

2^n subsets where n is the number of subsets. we have the empty subset [] then all of the rest

lets discuss the 3 steps

• you can see in some subsets we have a number, and other subsets we dont have that number.
• meaning there are 2 possibilities for 20. either in some subsets 20 is there and sometimes it is not.
• this means we will have to make 2 recursive calls. we can either take a value in our subsets, or we don't take that value in our subset.

.

I will show you the walkthrough of the decision tree for the example [1,2,3]. note that in our solutions, we use a soFar and we make the choice to not include the number first, and then we make the choice to include it. ****For the purposes of this example, I am going to do the opposite way, so I will be showing including the number first. So the subsets will be printed in the opposite to the output we have in the solution!

brace yourself, this might be a bit long :)