Practice Now
Java
Powerset
Set Theory
Algorithm
Programming

Obtaining a powerset of a set in Java

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
AlgorithmsData StructuresJava

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.
Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
Codemia
© 2026 Codemia
Resources
Legal
Social
All Rights Reserved.