# 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**.<br>

## Complexity

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

## Code

```java
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;
}

```

## <br>