Java Program to Find All Subsets of a Set

You can find all subsets of a set in Java by using recursion and backtracking, for example, by calling a method that adds or skips each element and prints all combinations like findSubsets(int[] arr, int index, List current).

Examples

Input[1]

Output[[], [1]]

Input[1, 2]

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

Input[]

Output[[]]

How to Think About It

To find all subsets, think of each element as having two choices: either include it in the current subset or exclude it. By exploring both choices for every element, you generate all possible combinations. This can be done by moving through the list recursively, building subsets step by step.

Algorithm

1

Start with an empty subset and the first element index.

2

At each step, decide to include the current element in the subset or not.

3

Recursively move to the next element with the updated subset.

4

When you reach the end of the list, record the current subset.

5

Repeat until all elements have been processed.

Code

java

import java.util.*;

public class Subsets {
    public static void findSubsets(int[] arr, int index, List<Integer> current, List<List<Integer>> result) {
        if (index == arr.length) {
            result.add(new ArrayList<>(current));
            return;
        }
        // Exclude current element
        findSubsets(arr, index + 1, current, result);
        // Include current element
        current.add(arr[index]);
        findSubsets(arr, index + 1, current, result);
        current.remove(current.size() - 1);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        List<List<Integer>> result = new ArrayList<>();
        findSubsets(arr, 0, new ArrayList<>(), result);
        System.out.println(result);
    }
}

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

Start with empty subset and index 0

current = [], index = 0

2

Exclude element 1, move to index 1

current = [], index = 1

3

Exclude element 2, move to index 2 (end)

current = [], index = 2 -> add [] to result

4

Include element 2, move to index 2 (end)

current = [2], index = 2 -> add [2] to result

5

Back to index 0, include element 1

current = [1], index = 1

6

Exclude element 2, move to index 2 (end)

current = [1], index = 2 -> add [1] to result

7

Include element 2, move to index 2 (end)

current = [1, 2], index = 2 -> add [1, 2] to result

Index	Current Subset	Action
0	[]	Exclude 1
1	[]	Exclude 2
2	[]	Add []
1	[]	Include 2
2	[2]	Add [2]
0	[]	Include 1
1	[1]	Exclude 2
2	[1]	Add [1]
1	[1]	Include 2
2	[1, 2]	Add [1, 2]

Why This Works

Step 1: Recursive Choice

At each element, the code chooses to either include or exclude it, exploring all paths.

Step 2: Base Case

When the index reaches the array length, the current subset is complete and added to the result.

Step 3: Backtracking

After exploring including an element, the code removes it to try other combinations without it.

Alternative Approaches

Iterative Bit Manipulation

java

import java.util.*;

public class SubsetsIterative {
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        int total = 1 << n; // 2^n subsets
        for (int i = 0; i < total; i++) {
            List<Integer> subset = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    subset.add(nums[j]);
                }
            }
            result.add(subset);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        System.out.println(subsets(arr));
    }
}

Uses bitwise operations to generate subsets iteratively; faster but less intuitive for beginners.

Using Streams (Java 8+)

java

import java.util.*;
import java.util.stream.*;

public class SubsetsStream {
    public static List<List<Integer>> subsets(int[] nums) {
        return IntStream.range(0, 1 << nums.length)
            .mapToObj(i -> IntStream.range(0, nums.length)
                .filter(j -> (i & (1 << j)) != 0)
                .mapToObj(j -> nums[j])
                .collect(Collectors.toList()))
            .collect(Collectors.toList());
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        System.out.println(subsets(arr));
    }
}

Uses Java streams for a functional style; concise but requires understanding of streams.

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

Time Complexity

There are 2^n subsets for n elements, and each subset can take up to O(n) time to copy or print.

Space Complexity

The result stores all subsets, requiring O(n * 2^n) space; recursion stack uses O(n) space.

Which Approach is Fastest?

Iterative bit manipulation is generally faster than recursion but less intuitive; recursion is easier to understand.

Approach	Time	Space	Best For
Recursive Backtracking	O(n * 2^n)	O(n * 2^n)	Easy to understand and implement
Iterative Bit Manipulation	O(n * 2^n)	O(n * 2^n)	Performance and bitwise practice
Java Streams	O(n * 2^n)	O(n * 2^n)	Concise functional style