78. Subsets

Intuition

This is a classic backtracking problem. For each number, we have two choices:

1. Include it in the current subset.

2. Exclude it.

By exploring both choices at each step, we can generate all possible subsets, i.e., the power set.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(N*2^{N})$

Code

List<List<Integer>> allSubsets = new LinkedList<>();

// Recursive function to generate all subsets
public void generateSubsets(int[] nums, int index, List<Integer> currentSubset) {
    
    // If we've considered all elements, add the current subset to the result
    if (index >= nums.length) {
        allSubsets.add(new ArrayList<>(currentSubset));
        return;
    }
    
    // Option 1: Exclude the current element and move to the next
    generateSubsets(nums, index + 1, currentSubset);
    
    // Option 2: Include the current element
    currentSubset.add(nums[index]);
    generateSubsets(nums, index + 1, currentSubset);

    // Backtrack: remove the last added element before returning
    currentSubset.remove(currentSubset.size() - 1);
}

public List<List<Integer>> subsets(int[] nums) {
    generateSubsets(nums, 0, new ArrayList<>(nums.length));
    return allSubsets;
}