Problem statement
You are given distinct integers. Return every subset that can be formed from those values. This is the Power Set problem; Subsets I instead asks for the sum of each subset.
A subset may contain any number of elements. It may contain all the values, just one value, or no values at all. The subset with no values is the empty subset, written as [].
The important input rules are:
- Values may be positive, zero, or negative. The supplied Power Set task permits 1–10 distinct values from −10 to 10.
- The input is a set, so its values are distinct. Duplicate handling is outside this problem’s contract.
- The official task starts with a nonempty set. A defensive implementation can still return
[[]]for an empty input. - Every element keeps its identity from the input. We choose each position at most once.
If the input contains n values, the result always contains exactly 2^n subsets. That output size is the main constraint. Even the best solution must create every one of those subsets.
Practice problem: Subsets / Power Set on LeetCode. The previous positive-only GFG variant remains covered by the same algorithm. Sorting is for predictable display, not for deciding which values can be selected.
Take/skip recursion and prefix generation enumerate the same power set. This article uses prefix generation and a static choose/return/undo trace. If input values repeat, use Subsets II so equal value-list answers are emitted only once.
Constraints & requirements
- INPUT
- Distinct integers; zero and negatives allowed. Power Set source: 1–10 values, −10–10.
- RETURN
- All possible subsets
- COUNT
- Exactly 2^n subsets
Examples 4 test cases
Example 1 Three values
- Input
[1, 2, 3]- Output
8 subsets
Checks the complete include and exclude tree.
Example 2 One value
- Input
[5]- Output
[[], [5]]
Checks the smallest nonempty set.
Example 3 Empty set
- Input
[]- Output
[[]]
Checks that the empty subset is still produced.
Example 4 Signed values
- Input
[-1, 0]- Output
[[], [-1], [-1, 0], [0]]
Selection depends on positions, not the sign of a value.
Hints Optional
01Think in choices
At each index there are two valid choices: include the current value or leave it out.
02Define the recursive state
Track the current index and the subset being built. When the index reaches the array length, one answer is complete.
03Undo before exploring the next branch
After exploring the include branch, remove the last value before exploring the exclude branch.
How to think before coding
Decide what one call promises: it emits the current prefix and every subset extending it using positions at or after startIndex. Saving at entry includes the empty subset. The loop chooses the next position, the child starts after it, and removal restores the parent. Save a copy, since the working list will keep changing. Increasing indices prevent order-only duplicates.
🐢 Brute force approach
A bitmask uses one bit for every input position. A 1 means the value is included, and a 0 means it is excluded.
For three values, the masks are:
000 -> [] 001 -> [1] 010 -> [2] 011 -> [1, 2] 100 -> [3] 101 -> [1, 3] 110 -> [2, 3] 111 -> [1, 2, 3]
The algorithm is:
- Copy and sort the input so values inside each subset are ordered without modifying the caller’s list.
- Enumerate every mask from
0to2^n - 1. - Scan every input position for the current mask.
- Add the value when its bit is set.
- Store the completed subset.
- Sort all generated subsets lexicographically to match the order shown in the problem examples.
This is correct because every element has one bit, and every possible arrangement of those bits appears exactly once.
Brute force Java solution
import java.util.ArrayList;
import java.util.Collections;
class Solution {
public ArrayList<ArrayList<Integer>> subsets(ArrayList<Integer> numbers) {
// Sort a copy so every subset is generated in the order used by the examples.
ArrayList<Integer> sortedNumbers = new ArrayList<>(numbers);
Collections.sort(sortedNumbers);
// The answer will contain one entry for every possible bit mask.
ArrayList<ArrayList<Integer>> allSubsets = new ArrayList<>();
int size = sortedNumbers.size();
long totalMasks = 1L << size;
// Visit every choice of included/excluded elements exactly once.
for (long mask = 0; mask < totalMasks; mask++) {
ArrayList<Integer> currentSubset = new ArrayList<>();
// Each set bit means that this value belongs in the current subset.
for (int index = 0; index < size; index++) {
if ((mask & (1L << index)) != 0) {
currentSubset.add(sortedNumbers.get(index));
}
}
allSubsets.add(currentSubset);
}
// Match the problem's lexicographic output order after generation.
allSubsets.sort(this::compareSubsets);
return allSubsets;
}
private int compareSubsets(
ArrayList<Integer> first,
ArrayList<Integer> second
) {
int sharedLength = Math.min(first.size(), second.size());
for (int index = 0; index < sharedLength; index++) {
int comparison = Integer.compare(first.get(index), second.get(index));
if (comparison != 0) {
return comparison;
}
}
return Integer.compare(first.size(), second.size());
}
}totalMasks is a long so the shift is not limited to the 31 usable magnitude bits of an int. In practice, the returned power set becomes too large long before a 64 bit mask is exhausted.
The copied input protects the caller from an unexpected sort. The comparator first checks corresponding values. If one subset is a prefix of another, the shorter subset comes first.
Generating the subsets takes Θ(n × 2^n) time because every mask checks all n positions. Sorting 2^n lists can take O(n² × 2^n) time in the worst case because there are O(2^n log 2^n) comparisons and a comparison may inspect O(n) values.
The returned output stores Θ(n × 2^n) integers. Excluding that output, the current subset and sorted input use O(n) space, while Java’s list sort may need O(2^n) temporary references.
This version is useful when learning bit manipulation, but the mask scan and final ordering work make it less natural for a recursion lesson.
🧪 Example
Input: [1, 2, 3] Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Each value has two choices: include it or leave it out. Three independent choices produce 2^3 = 8 subsets. The empty subset is valid because choosing nothing is still one possible selection.
A single value gives the smallest useful example:
Input: [7] Output: [[], [7]]
🧠 Understanding the problem
The task is not asking for one subset with a special property. It asks for the complete power set, which means every possible selection.
For [1, 2, 3], a valid answer may choose 1 and 3, giving [1, 3]. It may choose only 2, giving [2]. It must also include the two boundary choices: choose everything and choose nothing.
Only the choice made for each element matters. The sum of a subset, the order in which values were discovered and the size of the subset are not selection rules in this problem.
The challenge is completeness. We need a process that reaches every valid selection exactly once without losing track of earlier choices.
💡 Building the intuition
The most direct idea is to label every possible selection with a binary number.
For [1, 2, 3], the mask 101 means choose the first and third values. The mask 010 means choose only the second value. Walking from 000 to 111 covers all eight choices.
That idea is correct, but each mask makes us scan all n positions to ask which bits are set. If ordered output is required, we also have to sort the completed list afterward.
Recursion gives us another view. Instead of describing a subset after it has already been encoded, we build one selection at a time. We save the current selection, choose one unused value, explore everything that can follow it, then remove that value before trying the next choice.
The invariant is simple: currentSubset always contains exactly the values chosen on the path from the first call to the active call.
It remains true because we add one value immediately before the recursive call and remove that same value immediately after the call returns.
The key observation
Every subset can be represented by one unique sequence of increasing input indices. If recursion only moves forward, it reaches that sequence once and cannot build the same subset through another path.
This choose, explore and undo pattern is the foundation of backtracking.
⚡ Optimal approach
Backtracking constructs subsets directly in lexicographic order after sorting the values.
At each recursive call, the current selection is already a valid subset, so we save a copy. Then we try every value from startIndex onward. Moving the next call to index + 1 prevents a value from being chosen twice and prevents the search from moving backward.
The algorithm is:
- Copy and sort the input.
- Start with an empty
currentSubsetandstartIndex = 0. - Save a copy of the current subset.
- For each available index, choose its value.
- Recurse with the next index as the new starting point.
- Remove the chosen value after the recursive call returns.
- Continue with the next choice at the current level.
The maintained invariant is: before every call to buildSubsets, currentSubset contains the values selected by that call’s unique increasing sequence of indices.
The algorithm is correct because every valid subset has one such sequence. The empty sequence produces [], and every nonempty sequence is reached by choosing its indices from left to right.
Optimal Java solution
import java.util.ArrayList;
import java.util.Collections;
class Solution {
public ArrayList<ArrayList<Integer>> subsets(ArrayList<Integer> numbers) {
// Sort a copy so choosing indices from left to right is deterministic.
ArrayList<Integer> sortedNumbers = new ArrayList<>(numbers);
Collections.sort(sortedNumbers);
// The recursive helper owns the path and fills the answer list.
ArrayList<ArrayList<Integer>> allSubsets = new ArrayList<>();
buildSubsets(
0,
sortedNumbers,
new ArrayList<>(),
allSubsets
);
return allSubsets;
}
private void buildSubsets(
int startIndex,
ArrayList<Integer> numbers,
ArrayList<Integer> currentSubset,
ArrayList<ArrayList<Integer>> allSubsets
) {
// Every path is a valid subset, including the empty path at the root.
allSubsets.add(new ArrayList<>(currentSubset));
// Only consider later indices so no value is reused or visited twice.
for (int index = startIndex; index < numbers.size(); index++) {
// Choose this value before exploring all of its descendants.
currentSubset.add(numbers.get(index));
// The next call starts after the chosen index.
buildSubsets(index + 1, numbers, currentSubset, allSubsets);
// Undo the choice so the next sibling starts from the same path.
currentSubset.remove(currentSubset.size() - 1);
}
}
}The copy in allSubsets.add(new ArrayList<>(currentSubset)) is essential. Adding currentSubset itself would store the same mutable list reference many times. Later backtracking would then change every saved entry.
The last removal is equally important. It restores the path to the state owned by the current call before the loop tries another value.
The algorithm takes Θ(n × 2^n) time when output creation is counted accurately. There are 2^n subsets, and copying a subset may take O(n) time. Across the complete power set, exactly n × 2^(n - 1) values are copied.
The returned output uses Θ(n × 2^n) space. Excluding that output, the sorted copy, current path and recursive call stack use O(n) auxiliary space.
Backtracking does not beat the output lower bound. Its advantage is that it generates each path directly, avoids an extra global result sort and extends naturally to problems where invalid branches can be stopped early.
Read choose, return and undo in the code
Separate the mutable working path from saved answer copies. Follow add, the recursive call and remove in that order. Returning from the child does not itself remove an element from the shared list.
Use the dry-run table to track four facts together: the active call, the next Java operation, the current subset and the independent answer copies. The small diagram below isolates the undo statements.
choose 1 choose 2 choose 3
[] ───────> [1] ───────> [1, 2] ───────> [1, 2, 3]
<───────── remove 3
<────────────────────── remove 2🔍 Visual dry run

Read the text transcript
Use the optimal solution with numbers = [1, 2, 3]. The stack is written from the oldest call on the left to the active call on the right.
| Step | Call stack | Current subset | Action | Stored subsets |
|---|---|---|---|---|
| 1 | build(0, []) |
[] |
Save the current path | [[]] |
| 2 | build(0, []) |
[1] |
Choose 1 |
[[]] |
| 3 | build(0, []) → build(1, [1]) |
[1] |
Save the current path | [[], [1]] |
| 4 | build(0, []) → build(1, [1]) |
[1, 2] |
Choose 2 |
[[], [1]] |
| 5 | … → build(2, [1, 2]) |
[1, 2] |
Save the current path | [[], [1], [1, 2]] |
| 6 | … → build(2, [1, 2]) |
[1, 2, 3] |
Choose 3 |
[[], [1], [1, 2]] |
| 7 | … → build(3, [1, 2, 3]) |
[1, 2, 3] |
Save the current path | [[], [1], [1, 2], [1, 2, 3]] |
| 8 | … → build(2, [1, 2]) |
[1, 2] |
Return and remove 3 |
unchanged |
| 9 | build(0, []) → build(1, [1]) |
[1] |
Return and remove 2 |
unchanged |
| 10 | build(0, []) → build(1, [1]) |
[1, 3] |
Choose 3 |
unchanged |
| 11 | … → build(3, [1, 3]) |
[1, 3] |
Save the current path | … [1, 3] |
| 12 | build(0, []) |
[] |
Finish the 1 branch and remove 1 |
unchanged |
| 13 | build(0, []) → build(2, [2]) |
[2] |
Choose and save 2 |
… [2] |
| 14 | … → build(3, [2, 3]) |
[2, 3] |
Choose and save 3 |
… [2, 3] |
| 15 | build(0, []) → build(3, [3]) |
[3] |
Backtrack to root, choose and save 3 |
… [3] |
| 16 | empty | [] |
All loops are complete | all 8 subsets |
The current path follows this shape:
[]
└── [1]
├── [1, 2]
│ └── [1, 2, 3]
└── [1, 3]
└── [2]
└── [2, 3]
└── [3]The return from [1, 2, 3] does not erase that saved answer. It only removes 3 from the reusable working list, restoring [1, 2] so the caller can continue.
✅ Why the optimal solution works
Every active call owns one valid path. That remains true because the method chooses only values at or after startIndex, so indices are always increasing.
The method saves the current path before making another choice. This includes the empty path and every partial path, so subsets of every possible size are recorded.
No subset is skipped because its increasing index sequence is available as one route through the loops. No subset is repeated because a different route would require the same index sequence, which is impossible.
Each recursive call increases startIndex. Eventually there are no later positions to choose, the loop ends and the call returns. When the root loop ends, every valid route has been explored and the stored result is complete.
📊 Complexity comparison
| Approach | Time complexity | Space complexity | Main tradeoff |
|---|---|---|---|
| Brute force with bitmasks and result sorting | O(n² × 2^n) worst case |
Θ(n × 2^n) output, O(2^n + n) auxiliary |
Simple mapping from bits to choices, but scans every position and sorts the full result |
| Backtracking | Θ(n × 2^n) |
Θ(n × 2^n) output, O(n) auxiliary |
Requires careful undo logic, but generates ordered subsets directly |
Here, n is the number of input values. The returned output is separated from auxiliary working space because any solution must store 2^n lists when the full answer is returned.
If result order is not required, the bitmask version can skip its final sort. Its time then becomes Θ(n × 2^n), the same asymptotic bound as backtracking. Backtracking is still the more reusable pattern for later constraint based problems.
⚠️ Common mistakes
- Forgetting the empty subset. Save
currentSubsetat the start of every call, including the first call where it is empty. - Saving the mutable list itself. Store
new ArrayList<>(currentSubset). Otherwise every result entry points to the same list. - Forgetting to undo the choice. Remove the last value after recursion returns. Without that line, sibling branches inherit values that do not belong to them.
- Recursing with the wrong index. Pass
index + 1, notstartIndex + 1. The next call must begin after the value that was just chosen. - Modifying the caller’s input. Sort a copy unless the problem explicitly allows the method to change the supplied list.
- Adding duplicate handling to a distinct set problem. It is unnecessary here. If duplicates are allowed, sort first and skip equal values at the same recursion depth.
- Calling auxiliary space
O(1). The current path, sorted copy and call stack can all grow ton. - Claiming
O(2^n)without explaining output copies. Java creates lists containing a total ofn × 2^(n - 1)values, so the materialized result takesΘ(n × 2^n)time and space.
🧪 Edge cases and test cases
| Test case | Input | Expected output | What it verifies |
|---|---|---|---|
| Smallest valid set | [7] |
[[], [7]] |
Empty subset and one chosen value |
| Two values | [2, 4] |
[[], [2], [2, 4], [4]] |
Both branches and the undo step |
| Unsorted set | [3, 1, 2] |
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]] |
Input copy is sorted without changing the caller’s list |
| Three values | [1, 2, 3] |
8 subsets | The result count equals 2^3 |
| Four values | [1, 2, 3, 4] |
16 subsets | Every added value doubles the result count |
For [-1,0], the result is [[],[-1],[-1,0],[0]]. The sign does not change the take/skip decision. Duplicate values are still outside this distinct-input contract; they belong to Subsets II.
🧩 Pattern recognition
Look for phrases such as “all subsets,” “every combination,” “choose any number of elements” or “include or exclude each value.” They signal a decision tree where each element creates a choice.
Backtracking is especially useful when the problem later adds a rule such as a target sum, fixed subset size or validity constraint. The current subset becomes the state, choosing a value moves forward, and removing it restores the state for the next branch.
Remember the pattern as four actions:
save -> choose -> explore -> undo
📝 Final takeaway
Bitmasks describe each subset with binary choices, which makes a clear first solution. Backtracking builds the same choices directly and restores the current path after every recursive call.
The reusable idea is not just “use recursion.” It is to keep one valid state, make one choice, explore everything below that choice and undo it before moving to the next branch.
Practice next
Next lessonRecursion and Backtracking sectionReturn here as the next backtracking problems are published.