# Solving Subsets

To see the question, click **here**.

**Naive Approach**

The idea is to generate all possible subsets of a given array `nums`

using a backtracking approach. Initialize a result list to store all subsets and a temporary list `temp`

to store the current subset being explored. Assume a recursive function `f`

is then called to generate the subsets. The function `f`

takes the current index `i`

, the input array `nums`

, the temporary list `temp`

, the result list `result`

, and the length of the array `n`

as parameters. The function explores two possibilities at each step, including the current element `nums[i]`

in the subset or excluding it. When the element is included, it is added to `temp`

, and `f`

is called recursively with the next index `i + 1`

. When the element is excluded, it is removed from `temp`

, and `f`

is called again with the next index. This approach ensures that every possible subset is generated by exploring each element's inclusion or exclusion. Backtracking is used to remove the last added element from `temp`

before exploring the exclusion path, ensuring that all combinations are considered. The base case of the recursion occurs when `i`

equals `n`

, meaning all elements have been considered. At this point, a deep copy of the current `temp`

list is added to the `result`

list, ensuring that the current subset is stored before backtracking.

```
// TC: O(2^n)
// SC: O(n)
import java.util.List;
import java.util.ArrayList;
class Subsets {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
int n = nums.length;
f(0, nums, temp, result, n);
return result;
}
public void f(int i, int[] nums, List<Integer> temp, List<List<Integer>> result, int n) {
if (i == n) {
result.add(new ArrayList<>(temp));
return;
}
// include
temp.add(nums[i]);
f(i + 1, nums, temp, result, n);
// exclude
temp.remove(temp.size() - 1);
f(i + 1, nums, temp, result, n);
}
public static void main(String args[]) {
Subsets s = new Subsets();
int[] nums = { 1, 2, 3 };
System.out.println(s.subsets(nums));
}
}
```

**Performance**

The time complexity of the `subsets`

method is O(2^n) because we have two choices for each element in the input array - either include it in the subset or exclude it. This results in a binary tree structure with 2^n leaf nodes, each representing a subset. The space complexity is O(n) because we are using a temporary list to store the current subset being generated, and the recursion depth can go up to n levels in the worst-case scenario.

**Refined Approach**

By incrementing the `start`

index with each recursive call, the function ensures that it doesn't revisit elements already considered for the current subset. This prevents the generation of duplicate subsets and reduces the overall number of recursive calls. It's important to note that the fundamental time complexity might not drastically change due to the nature of the problem.

```
// TC: O(2^n)
// SC: O(n)
import java.util.List;
import java.util.ArrayList;
class Subsets {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
f(nums, result, new ArrayList<>(), 0);
return result;
}
public void f(int[] nums, List<List<Integer>> result, List<Integer> temp, int start) {
result.add(new ArrayList<>(temp)); // Add the current subset to the result
for (int i = start; i < nums.length; i++) {
temp.add(nums[i]); // Include the current element in the subset
f(nums, result, temp, i + 1); // Recursively generate subsets starting from the next index
temp.remove(temp.size() - 1); // Backtrack by removing the current element from the subset
}
}
public static void main(String args[]) {
Subsets s = new Subsets();
int[] nums = { 1, 2, 3 };
System.out.println(s.subsets(nums));
}
}
```

**Performance**

The time complexity of the `subsets`

method is O(2^n) because we have two choices for each element in the input array - either include it in the subset or exclude it. This results in a total of 2^n possible subsets. The space complexity is O(n) because we use recursion to generate subsets, and the recursive stack can go up to a depth of n. Additionally, the space complexity of the result list is also O(n), as it can contain up to 2^n subsets, each with a maximum size of n.

Thank you for reading!

Check out other DSA patterns **here**.

You can support me by **buying me a book****.**