Problem:
Generate all subsets of {1,2,3}
👉 Subsets are like: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3].
Key points you need:
-
List<Integer> → Just a resizable array.
Example: List<Integer> a = new ArrayList<>();
You can:
Think of it like Python’s list or C++ vector.
-
List<List<Integer>> → means a list of lists.
Why? Because we want to store all subsets (each subset itself is a list).
Example:
Now your function step-by-step:
-
index → where we are in the array.
-
nums → original input {1,2,3}.
-
current → current subset we are building.
-
result → stores all subsets.
Base case:
👉 If we reached the end of array → save the current subset.
new ArrayList<>(current) = copy of current (otherwise all subsets would change together).
Choices:
Skip the element.
Take the element, explore, then remove it (to undo choice for next branch).
Dry run with {1,2,3}:
-
Start [] at index=0
-
Exclude 1 → go next
-
Exclude 2 → go next
-
Exclude 3 → add []
-
Include 3 → add [3]
-
Include 2 →
-
Exclude 3 → add [2]
-
Include 3 → add [2,3]
-
Include 1 →
-
Exclude 2 →
-
Exclude 3 → add [1]
-
Include 3 → add [1,3]
-
Include 2 →
-
Exclude 3 → add [1,2]
-
Include 3 → add [1,2,3]
Result = [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]
✅ That’s why we need List<List<Integer>> → to store all subsets.
CODE:
import java.util.*; // (My Mistake) -> forgot to add this which had 'List' errors atleast 8
public class Main
{
static void findSubsets(int index, int[] nums, List<Integer> current, List<List<Integer>> result) {
// Base case: if index == nums.length, add the subset
if(index == nums.length) {
result.add(new ArrayList<>(current)); // dynamic size of ArrayList no worry of size
return;
}
// Choice 1: Exclude nums[index]
findSubsets(index+1, nums, current, result);
// Choice 2: Include nums[index]
current.add(nums[index]);
findSubsets(index+1, nums, current, result);
// Backtrack (Remove last added element)
current.remove(current.size() -1);
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
List<List<Integer>> result = new ArrayList<>();
findSubsets(0, nums, new ArrayList<>(), result);
System.out.println(result);
}
}
