Python Program to Find All Subsets of a Set

You can find all subsets of a set in Python using recursion or iteration; for example, use def subsets(s): return [[]] if not s else subsets(s[1:]) + [[s[0]] + x for x in subsets(s[1:])] to get all subsets.

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 including or excluding each element one by one. For each element, you create new subsets by adding it to existing subsets. This way, you build all possible combinations step by step.

Algorithm

1

Start with an empty list of subsets containing only the empty subset.

2

For each element in the input set, take all existing subsets and add the current element to them to create new subsets.

3

Add these new subsets to the list of all subsets.

4

After processing all elements, return the list of all subsets.

Code

python

def find_subsets(s):
    subsets = [[]]
    for elem in s:
        subsets += [curr + [elem] for curr in subsets]
    return subsets

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

Output

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

Dry Run

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

1

Initialize subsets

subsets = [[]]

2

Process element 1

New subsets = [[] + [1]] = [[1]]; subsets = [[]] + [[1]] = [[], [1]]

3

Process element 2

New subsets = [[elem] + [2] for elem in subsets] = [[2], [1, 2]]; subsets = [[], [1]] + [[2], [1, 2]] = [[], [1], [2], [1, 2]]

Iteration	Current Element	Subsets After Iteration
0	None	[[]]
1	1	[[], [1]]
2	2	[[], [1], [2], [1, 2]]

Why This Works

Step 1: Start with empty subset

We begin with a list containing only the empty subset [] because every set has an empty subset.

Step 2: Add new subsets for each element

For each element, we add it to all existing subsets to create new subsets, doubling the total subsets.

Step 3: Combine old and new subsets

We combine the old subsets with the new ones to keep track of all possible subsets formed so far.

Alternative Approaches

Recursion

python

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

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

Uses recursion to build subsets by including or excluding the first element; elegant but may hit recursion limits on large sets.

Using itertools

python

from itertools import combinations

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

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

Uses Python's built-in itertools for concise code; efficient and readable but requires importing a module.

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

Time Complexity

Generating all subsets requires processing each element for every existing subset, doubling subsets each time, resulting in O(n * 2^n) time.

Space Complexity

We store all subsets, which can be up to 2^n subsets, so space complexity is O(2^n).

Which Approach is Fastest?

Iterative and itertools methods are generally faster and use less stack space than recursion, especially for larger sets.

Approach	Time	Space	Best For
Iterative	O(n * 2^n)	O(2^n)	General use, large sets
Recursion	O(n * 2^n)	O(2^n)	Smaller sets, clear logic
itertools	O(n * 2^n)	O(2^n)	Concise code, built-in functions