Obtaining a powerset of a set in Java

Java

Powerset

Set Theory

Algorithm

Programming

Obtaining a powerset of a set in Java

Master System Design with Codemia

Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.

Start Practicing Learn More

Introduction

The power set of a set contains every possible subset, including empty and full subsets. For a set with n elements, the power set size is 2^n, so any complete algorithm is inherently exponential in output. In Java, the best implementation choice depends on whether you need all subsets in memory or streamed one by one.

Core Sections

Backtracking implementation

Backtracking is expressive and easy to customize for constraints.

java

1import java.util.ArrayList;
2import java.util.List;
3
4public class PowerSetBacktracking {
5    public static <T> List<List<T>> powerSet(List<T> items) {
6        List<List<T>> result = new ArrayList<>();
7        dfs(items, 0, new ArrayList<>(), result);
8        return result;
9    }
10
11    private static <T> void dfs(List<T> items, int index, List<T> current, List<List<T>> result) {
12        if (index == items.size()) {
13            result.add(new ArrayList<>(current));
14            return;
15        }
16
17        dfs(items, index + 1, current, result);
18
19        current.add(items.get(index));
20        dfs(items, index + 1, current, result);
21        current.remove(current.size() - 1);
22    }
23
24    public static void main(String[] args) {
25        System.out.println(powerSet(List.of("a", "b", "c")));
26    }
27}

This pattern is useful when later you want pruning rules.

Bitmask implementation

Bitmask enumeration is iterative and compact.

java

1import java.util.ArrayList;
2import java.util.List;
3
4public class PowerSetBitmask {
5    public static <T> List<List<T>> powerSet(List<T> items) {
6        int n = items.size();
7        int total = 1 << n;
8        List<List<T>> result = new ArrayList<>(total);
9
10        for (int mask = 0; mask < total; mask++) {
11            List<T> subset = new ArrayList<>();
12            for (int i = 0; i < n; i++) {
13                if ((mask & (1 << i)) != 0) {
14                    subset.add(items.get(i));
15                }
16            }
17            result.add(subset);
18        }
19
20        return result;
21    }
22}

For small to medium n, this is often straightforward and fast.

Working with `Set` input

Since Java Set has no guaranteed order unless using ordered variants, convert to a list first for deterministic subset ordering.

java

1import java.util.ArrayList;
2import java.util.LinkedHashSet;
3import java.util.List;
4import java.util.Set;
5
6Set<String> input = new LinkedHashSet<>(List.of("x", "y", "z"));
7List<String> ordered = new ArrayList<>(input);

Deterministic ordering helps tests and reproducible outputs.

Memory aware streaming approach

When n grows, storing all subsets can exhaust heap quickly. Instead, consume subsets as generated.

java

1import java.util.ArrayList;
2import java.util.List;
3import java.util.function.Consumer;
4
5public class PowerSetStreaming {
6    public static <T> void visitPowerSet(List<T> items, Consumer<List<T>> consumer) {
7        visit(items, 0, new ArrayList<>(), consumer);
8    }
9
10    private static <T> void visit(List<T> items, int index, List<T> current, Consumer<List<T>> consumer) {
11        if (index == items.size()) {
12            consumer.accept(new ArrayList<>(current));
13            return;
14        }
15
16        visit(items, index + 1, current, consumer);
17        current.add(items.get(index));
18        visit(items, index + 1, current, consumer);
19        current.remove(current.size() - 1);
20    }
21}

Streaming keeps memory proportional to recursion depth instead of full output size.

Complexity expectations

Time complexity is O(n * 2^n) when accounting for subset construction work. Space complexity varies:

full materialization uses O(n * 2^n) storage.
streaming uses O(n) auxiliary stack plus consumer state.

Common Pitfalls

Expecting polynomial runtime for full power set generation. Output size is exponential.
Using unordered input sets and assuming stable subset order. Convert to ordered list first.
Storing all subsets for large n and exhausting memory. Use streaming consumer approach.
Forgetting empty subset and failing mathematical completeness. Include empty case explicitly.
Mutating shared subset lists without copying at leaf nodes. Clone current subset before storing.

Summary

Power set generation is inherently exponential because output count is 2^n.
Backtracking and bitmask methods are both valid in Java.
Deterministic ordering requires list conversion from set inputs.
Streaming subsets is essential for larger inputs.
Correct copying and clear complexity expectations prevent subtle bugs.

Obtaining a powerset of a set in Java

Master System Design with Codemia

Introduction

Core Sections

Backtracking implementation

Bitmask implementation

Working with Set input

Memory aware streaming approach

Complexity expectations

Common Pitfalls

Summary

Working with `Set` input