Subsets
Problem
Given an integer array nums of unique elements, return all possible subsets (the power set).
Examples
Example 1
Input: nums = [1,2,3]
Output: [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
Explanation: All 2^3 = 8 subsets, including the empty set and the full set.
Constraints
- •
1 <= nums.length <= 10
Hints
Hint 1
Every element has exactly two states at each decision point: included in the current subset, or not — that binary choice per element is the whole recursion tree.
Hint 2
This is the choose-explore-unchoose template directly: for each element, choose to include it, recurse, then unchoose (remove it) before trying without it.
Hint 3
The current partial subset at EVERY point in the recursion is itself a valid answer — not just at the leaves — since a subset can be any size.
Solutions
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
result.add(new ArrayList<>(current)); // every partial state is a valid subset — add it here, not just at a base case
for (int i = start; i < nums.length; i++) {
current.add(nums[i]); // CHOOSE
backtrack(nums, i + 1, current, result); // EXPLORE
current.remove(current.size() - 1); // UNCHOOSE
}
}Time: O(n * 2^n) · Space: O(n) recursion depth, excluding output