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.