Editor

Python Program to Generate All Subsets of a Set

Intermediate · Recursion

A subset is any selection of items from a set, including the empty selection and the whole set. The set {1, 2, 3} has 8 subsets, and in general a set of n items has 2^n of them, also called its power set. This program builds them with recursion: every subset either leaves out the first item or includes it.

Program

generate_subsets.py
def subsets(items):
# Base case: an empty list has exactly one subset, the empty one
if len(items) == 0:
return [[]]
first = items[0]
# Recursive step: find the subsets of the other items...
without_first = subsets(items[1:])
# ...then make a copy of each one with the first item added
with_first = []
for s in without_first:
with_first.append([first] + s)
return without_first + with_first
items = [1, 2, 3]
result = subsets(items)
print("Subsets of", items)
for s in result:
print("{" + ", ".join(str(x) for x in s) + "}")
print("Total:", len(result), "= 2 **", len(items))
Output
Subsets of [1, 2, 3]
{}
{3}
{2}
{2, 3}
{1}
{1, 3}
{1, 2}
{1, 2, 3}
Total: 8 = 2 ** 3

How it works

  1. The base case is an empty list, whose only subset is the empty set, so the function returns [[]], a list holding one empty list.
  2. For a longer list, the function sets the first item aside and calls itself to get all the subsets of the rest.
  3. Every subset of the full list either leaves the first item out, so it is one of those, or puts it in, so it is one of those with first added.
  4. Each extra item therefore doubles the number of subsets, 1, 2, 4, 8, which is why a set of n items has 2^n of them.
  5. The subsets are kept as lists, because a Python set cannot hold other sets, and printed with curly braces to look like sets.

Other ways to write it

Using itertools.combinations()

Using itertools.combinations()
from itertools import combinations
items = [1, 2, 3]
for size in range(len(items) + 1):
for combo in combinations(items, size):
print(f"Size {size}:", list(combo))
Output
Size 0: []
Size 1: [1]
Size 1: [2]
Size 1: [3]
Size 2: [1, 2]
Size 2: [1, 3]
Size 2: [2, 3]
Size 3: [1, 2, 3]

combinations(items, size) gives every way to choose size items, so looping over every size from 0 to n lists all the subsets, grouped by size.

Using binary numbers

Using binary numbers
items = ["a", "b", "c"]
n = len(items)
for mask in range(2 ** n): # 0 to 7
subset = []
for i in range(n):
if mask & (1 << i): # is bit i of mask switched on?
subset.append(items[i])
print(format(mask, "03b"), subset)
Output
000 []
001 ['a']
010 ['b']
011 ['a', 'b']
100 ['c']
101 ['a', 'c']
110 ['b', 'c']
111 ['a', 'b', 'c']

Each number from 0 to 2^n - 1 is a pattern of bits, and bit i, counting from the right, says whether item i is in, so 101 means a and c; this version needs no recursion.

Try it yourself

Add a fourth item to items and check that the total becomes 16.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises