Understanding Subsets in Java

Introduction & Problem Explanation

The Subsets problem (often referred to as generating the Power Set) asks us to return all possible subsets of a set of unique integers, nums.

A subset is a selection of elements from the original set, where order does not matter, and the selection can include no elements (the empty set []) or all elements. For example, if nums = [1, 2, 3], the power set is:
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]. Since the total number of subsets for a set of size n is exactly 2n, any algorithm solving this problem has a minimum exponential time complexity of O(2n). Backtracking is the standard, cleanest way to build these subsets programmatically.

The Algorithmic Approach

DFS Backtracking Search (O(2ⁿ) Time, O(n) Space)

We traverse the state space recursively. Starting from index 0:

• Record Current Path: In each recursive call, the current state of our path is a valid subset. We create a copy of the path and add it to our results list.
• Iterate and Branch: We loop from the current start index to the end of the array. For each index i:
  1. We add nums[i] to our active path.
  2. We recurse forward by calling the function with start = i + 1. This ensures we only add elements to the right of the current element, preventing duplicate combinations (like [1, 2] and [2, 1]).
  3. When the recursive call returns, we perform the backtracking step by removing the last element we added (nums[i]) from the active path, restoring the path to its previous state.

The depth of our recursion tree is at most n, resulting in an auxiliary space complexity of O(n).

Step-by-Step Execution Walkthrough

Let's trace the backtracking function for nums = [1, 2, 3]:

1. Step 1 (Root Call): backtrack(start=0, path=[]).
   • Add copy of path to result. result = [[]].
   • Loop starts at i = 0. Add nums[0] (1) to path. Path is now [1].
2. Step 2 (Recurse i=0): Call backtrack(start=1, path=[1]).
   • Add copy: result = [[], [1]].
   • Loop starts at i = 1. Add nums[1] (2). Path is now [1, 2].
3. Step 3 (Recurse i=1): Call backtrack(start=2, path=[1, 2]).
   • Add copy: result = [[], [1], [1, 2]].
   • Loop starts at i = 2. Add nums[2] (3). Path is now [1, 2, 3].
4. Step 4 (Recurse i=2): Call backtrack(start=3, path=[1, 2, 3]).
   • Add copy: result = [[], [1], [1, 2], [1, 2, 3]].
   • Loop at start=3 doesn't run. Return.
5. Step 5 (Backtrack from 3): In Step 3, we pop 3. Path goes back to [1, 2].
   • Loop for start=2 ends. Return.
6. Step 6 (Backtrack from 2): In Step 2, we pop 2. Path goes back to [1].
   • Loop continues in Step 2 at i = 2. Add nums[2] (3). Path is now [1, 3].
   • Call backtrack(start=3, path=[1, 3]). Saves it. Returns. Pops 3.
7. Step 7 (Continue Backtracking): The execution continues this way until all combinations are explored, ending with the collection of all 8 subsets.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• res.add(new ArrayList<>(path));: Creates a deep copy of the active path. Since Java passes references by value, adding path directly would result in a list of empty lists at the end.
• path.add(nums[i]); ... path.remove(path.size() - 1);: The backtrack sandwich. We explore all paths containing nums[i], and then clean up by removing it to test combinations without it.
• backtrack(i + 1, ...);: Increments start boundary to guarantee we only move forward, preventing duplicate entries.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Subsets {

    // Backtracking Search: Time O(2^N), Space O(N)
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null) {
            return result;
        }
        
        // Start backtracking from index 0
        backtrack(0, nums, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int start, int[] nums, List<Integer> path, List<List<Integer>> result) {
        // Add the current path subset to our result (must deep copy)
        result.add(new ArrayList<>(path));

        for (int i = start; i < nums.length; i++) {
            // 1. Choose: add current element
            path.add(nums[i]);

            // 2. Explore: recurse to next elements
            backtrack(i + 1, nums, path, result);

            // 3. Unchoose: backtrack by removing the last element
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        Subsets solver = new Subsets();
        int[] nums = {1, 2, 3};

        System.out.println("--- Subsets (Power Set) Demonstration ---");
        System.out.println("Input Array: " + Arrays.toString(nums));
        List<List<Integer>> powerSet = solver.subsets(nums);
        System.out.println("Generated Subsets: " + powerSet);
    }
}

Conclusion

The Subsets problem is a classic introduction to state-space generation. By using backtracking, we recursively walk the decision tree, choosing to include or exclude elements, and build the entire power set in optimal time and memory.