Generate Subsets in Java
intermediate· Recursion · Recursion
Problem
The power set of a collection is every possible subset of it, including the empty subset — for n elements there are always exactly 2^n of them, since each element is independently either in or out.
Given a short array, print every subset of its elements.
Input
[1, 2, 3]
Output
[]
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]
Java Program
Java
import java.util.ArrayList;
import java.util.List;
public class GenerateSubsets {
static void generate(int[] nums, int index, List<Integer> current) {
if (index == nums.length) {
System.out.println(current);
return;
}
generate(nums, index + 1, current); // exclude nums[index]
current.add(nums[index]);
generate(nums, index + 1, current); // include nums[index]
current.remove(current.size() - 1); // backtrack
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
generate(nums, 0, new ArrayList<>());
}
}Output
[]
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]
Core Logic
Branching at every element into 'leave it out' and 'put it in', and only printing once every element has been decided, visits every combination of in/out choices exactly once.
How It Works
- 1
generate(nums, index, current)tracks which elements have been decided so far incurrent, and which element is being decided next viaindex. - 2The base case
index == nums.lengthmeans every element has been decided, socurrentis a complete subset, printed as-is. - 3The exclude branch recurses immediately, without touching
current— this explores every subset that leaves the current element out. - 4The include branch adds the current element, recurses, then removes it again — that removal is the backtrack step, undoing the choice so the next branch starts clean.
For
[1, 2, 3], deciding element 3 first branches into excluding it (giving [] and [2]-based subsets) and including it (giving [3] and [2, 3]), before element 1 is even considered — the exact order printed follows how the recursion unwinds.💡
Key Point: Removing the element after the include branch returns is what lets current be reused across every branch of the recursion tree, instead of needing a fresh list built for each subset.
Complexity
Time Complexity: O(2^n)Space Complexity: O(n)
Why: There are 2^n total subsets to print, but the recursion only ever nests n calls deep, one per element decision.
Key Concepts
recursionbacktrackinginclude/exclude