Find Subsets in Java (backtracking problem)

 

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:

1. List<Integer> → Just a resizable array.
   Example: List<Integer> a = new ArrayList<>();
   You can:

   • a.add(5); → adds 5

   • a.remove(0); → removes first element

   • a.size(); → gives length

   Think of it like Python’s list or C++ vector.

2. List<List<Integer>> → means a list of lists.
   Why? Because we want to store all subsets (each subset itself is a list).
   Example:

   [ [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3] ]
   

---

Now your function step-by-step:

static void findSubsets(int index, int[] nums, List<Integer> current, List<List<Integer>> result) {

• 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(index == nums.length) {
    result.add(new ArrayList<>(current));
    return;
}

👉 If we reached the end of array → save the current subset.
new ArrayList<>(current) = copy of current (otherwise all subsets would change together).

---

Choices:

// Choice 1: Exclude nums[index]
findSubsets(index+1, nums, current, result);

Skip the element.

// Choice 2: Include nums[index]
current.add(nums[index]);
findSubsets(index+1, nums, current, result);
current.remove(current.size() -1); // backtrack

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);

}

}