Power Set of an Array
Solve this Problemnums whose values never repeat. Produce its power set — every subset that can be formed from it, from the empty subset all the way up to the full array itself, with nothing missing and nothing duplicated.
Each element has exactly two states — in the subset, or not — so an array of n elements has exactly 2ⁿ possible subsets. That count is fixed by the problem itself, not by how it's solved: any correct approach visits every one of those 2ⁿ combinations at least once.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ nums.length ≤ 10 - ◆
-10 ≤ nums[i] ≤ 10 - ◆
Every value in nums is distinct
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Iterative — Bitmask Enumeration
GoodEvery subset corresponds to exactly one n-bit number: bit i decides whether nums[i] is included. Loop a counter from 0 to 2ⁿ - 1, and for each value, read off which bits are set to build that subset. Simple and direct, but every subset is built as a standalone pass over all n bits rather than reusing work from the subset built just before it.
O(2ⁿ · n)O(2ⁿ · n)1class Solution {
2 public int[][] subsets(int[] nums) {
3 int n = nums.length;
4 List<int[]> result = new ArrayList<>();
5 for (int mask = 0; mask < (1 << n); mask++) {
6 List<Integer> subset = new ArrayList<>();
7 for (int i = 0; i < n; i++) {
8 if ((mask & (1 << i)) != 0) {
9 subset.add(nums[i]);
10 }
11 }
12 int[] row = new int[subset.size()];
13 for (int j = 0; j < row.length; j++) {
14 row[j] = subset.get(j);
15 }
16 result.add(row);
17 }
18 return result.toArray(new int[0][]);
19 }
20}Optimal — Backtracking (Include / Exclude)
OptimalWalk a single mutable path through a decision tree: at every node, the current path is itself a valid subset — record it — then try adding each remaining element one at a time, recursing, and removing it again before trying the next. Same output size as the bitmask approach, but it builds every subset incrementally from the one before it rather than from scratch, and this exact include/exclude shape is what problems like Subsets II and Combination Sum build on directly.
O(2ⁿ · n)O(n) extra1class Solution {
2 public int[][] subsets(int[] nums) {
3 List<int[]> result = new ArrayList<>();
4 List<Integer> path = new ArrayList<>();
5 backtrack(nums, 0, path, result);
6 return result.toArray(new int[0][]);
7 }
8
9 private void backtrack(int[] nums, int start, List<Integer> path, List<int[]> result) {
10 int[] row = new int[path.size()];
11 for (int j = 0; j < row.length; j++) {
12 row[j] = path.get(j);
13 }
14 result.add(row);
15 for (int i = start; i < nums.length; i++) {
16 path.add(nums[i]);
17 backtrack(nums, i + 1, path, result);
18 path.remove(path.size() - 1);
19 }
20 }
21}