Python Program to Print All Subsets of a Set

You can print all subsets of a set in Python using recursion by defining a function that either includes or excludes each element, like def subsets(s): if not s: return [[]] else: rest = subsets(s[1:]); return rest + [[s[0]] + r for r in rest].

Examples

Input[1]

Output[[], [1]]

Input[1, 2]

Output[[], [2], [1], [1, 2]]

Input[]

Output[[]]

How to Think About It

To find all subsets of a set, think about each element and decide if it should be in a subset or not. Start with an empty subset and for each element, create new subsets by adding that element to existing subsets. This way, you build all possible combinations step by step.

Algorithm

1

If the set is empty, return a list containing an empty subset.

2

Take the first element and find all subsets of the remaining elements recursively.

3

Create new subsets by adding the first element to each of the subsets found in the previous step.

4

Combine the subsets without the first element and the new subsets with the first element.

5

Return the combined list of subsets.

Code

python

def subsets(s):
    if not s:
        return [[]]
    rest = subsets(s[1:])
    return rest + [[s[0]] + r for r in rest]

# Example usage
my_set = [1, 2, 3]
all_subsets = subsets(my_set)
print(all_subsets)

Output

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

Dry Run

Let's trace the input [1, 2] through the code

1

Call subsets with [1, 2]

s = [1, 2]

2

Call subsets with [2]

s = [2]

3

Call subsets with [] (empty list)

s = [] returns [[]]

4

Build subsets for [2]

rest = [[]], new subsets = [[2]], combined = [[], [2]]

5

Build subsets for [1, 2]

rest = [[], [2]], new subsets = [[1], [1, 2]], combined = [[], [2], [1], [1, 2]]

Call	rest	new subsets	combined result
subsets([])	N/A	N/A	[[]]
subsets([2])	[[]]	[[2]]	[[], [2]]
subsets([1, 2])	[[], [2]]	[[1], [1, 2]]	[[], [2], [1], [1, 2]]

Why This Works

Step 1: Base case returns empty subset

When the input set is empty, the only subset is the empty set itself, so the function returns [[]].

Step 2: Recursive call finds subsets of smaller set

The function calls itself with the rest of the set (excluding the first element) to find all subsets without the first element.

Step 3: Combine subsets with and without first element

It then creates new subsets by adding the first element to each subset found, and combines these with the subsets without the first element.

Alternative Approaches

Iterative approach using bit manipulation

python

def subsets_iterative(s):
    n = len(s)
    result = []
    for i in range(2**n):
        subset = []
        for j in range(n):
            if i & (1 << j):
                subset.append(s[j])
        result.append(subset)
    return result

print(subsets_iterative([1, 2, 3]))

This method uses binary numbers to represent subsets and is efficient for small sets but less intuitive.

Using itertools combinations

python

from itertools import combinations

def subsets_itertools(s):
    result = []
    for r in range(len(s)+1):
        for combo in combinations(s, r):
            result.append(list(combo))
    return result

print(subsets_itertools([1, 2, 3]))

This uses Python's built-in library for a clean and readable solution but requires importing itertools.

Complexity: O(n * 2^n) time, O(n * 2^n) space

Time Complexity

There are 2^n subsets for a set of size n, and each subset can take up to O(n) time to copy or create, so total time is O(n * 2^n).

Space Complexity

The output list stores all subsets, which requires O(n * 2^n) space because each subset can have up to n elements.

Which Approach is Fastest?

The iterative bit manipulation and itertools methods have similar time complexity but may be faster in practice due to less recursion overhead.

Approach	Time	Space	Best For
Recursive	O(n * 2^n)	O(n * 2^n)	Clear logic and teaching recursion
Iterative Bit Manipulation	O(n * 2^n)	O(n * 2^n)	Performance on small sets, no recursion
itertools Combinations	O(n * 2^n)	O(n * 2^n)	Concise code using standard library