Problem Statement

Given a list of distinct items (or a set), print out all of its subset lists.

Input:

[1, 2, 3, 4]

Output:

:empty set:
1
1,2
1,3
1,4
1,2,3
1,2,4
1,3,4
1,2,3,4
2
2,3
2,4
2,3,4
3
3,4
4

Proposed Solution

For each given list, I would need to figure out how many set of subsets there are. In this case, the total number of subsets for a given list is 2^n, where n is the total number of items in the list.

The reason it is 2^n is because: For each item in the list, you have 2 possible choices to take; Append an item to it, or don’t. And since you have n items, you have a total of 2^n choices.

After figuring out how many total subsets there are, that can be the terminating condition in a recursive solution, something like

if len(answer) == int(math.pow(2,len(myList))):
        return answer

In each step of the code, we need to clone the list into two to model them as the two potential choices; adding an item, or not adding an item. We add an item to each element in one list (adding an item), and preserve the original list (not adding an item), and join the two results together

Example:

Given List = [1, 2]

Step 1: Add 1

Result = {}, {1}, {2}, {1,2}

We can see that taking the union of sets that add, and sets that do not add will give us the total subsets. The above is the pseudocode for the main body of code for our solution. Given that we have an idea of what the terminating condition will be like, we can model this as a recursive solution.

In each recursion, we should

1. Check if total number of items in the set is = 2^(length of list)
2. Clone the given set
3. Add the item to one of the set
4. Take the union of the original set and the modified set
5. Go back to step 1

Translated to python3,

def printPattern(givenList, result, totalSubsets):
        if len(result) == totalSubsets:
                return result

        # models not adding
        clonedResult = copy.deepcopy(result)

        itemToAdd = givenList[0]

        # omititng the item we just added in the next recursion
        newList = givenList[1:]

        # adding an item to each item in the list
        for item in result:
                item.append(itemToAdd)

        # taking the union of both the results
        result += clonedResult

        return printPattern(newList, result, totalSubsets)

Read here to understand why I used deepcopy: How to clone or copy a list?

That’s it!