78. Subsets

Description

The problem requires generating all possible subsets of a given set of integers. This includes the empty subset, single-element subsets, and all possible combinations of the elements in the set.

Intuition

The intuitive approach to solving this problem involves using recursion and backtracking. By exploring each element in the set, we can either include it in the current subset or exclude it, thus generating all possible combinations.

Approach

1. Initialization: - Create an empty list res to store the final subsets. - Create an empty list subset to store the current subset being constructed.
2. Recursive Function: - Define a helper method createSubset that takes the current index index, the current subset being constructed, and the result list res. - If the current index index equals the length of nums, add a copy of the current subset to the result list and return. - Add the current element nums[index] to the subset and call the function recursively with the next index. - After exploring that path, remove the current element from the subset and call the function recursively with the next index.
3. Return the Result: - The main method subsets starts the recursion from the first index and returns the result list.

This approach ensures that all possible subsets are generated by considering each element's inclusion or exclusion in the subsets.

Complexity

Time Complexity:

O(2^n), where n is the number of elements in the input list. This is because each element can either be included or excluded, leading to 2^n possible subsets.

Space Complexity:

O(n), where n is the number of elements in the input list. This space is used by the recursion stack and the temporary list subset during the backtracking process.

Code

C++

class Solution {
public:
    vector> subsets(vector& nums) {
        vector> res;
        vector subset;
        createSubset(nums, 0, subset, res);
        return res;
    }
private:
    void createSubset(vector& nums, int i, vector& subset, vector>& res) {
        if (i == nums.size()) {
            res.push_back(subset);
            return;
        }
        subset.push_back(nums[i]);
        createSubset(nums, i + 1, subset, res);
        subset.pop_back();
        createSubset(nums, i + 1, subset, res);
    }
};

Python

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        subset = []
        self.createSubset(nums, 0, subset, res)
        return res

    def createSubset(self, nums: List[int], index: int, subset: List[int], res: List[List[int]]) -> None:
        if index == len(nums):
            res.append(subset.copy())
            return
        subset.append(nums[index])
        self.createSubset(nums, index + 1, subset, res)
        subset.pop()
        self.createSubset(nums, index + 1, subset, res)

Java

class Solution {
    public List> subsets(int[] nums) {
        List> res = new ArrayList<>();
        List subset = new ArrayList<>();
        createSubset(nums, 0, subset, res);
        return res;
    }

    private void createSubset(int[] nums, int index, List subset, List> res) {
        if (index == nums.length) {
            res.add(new ArrayList<>(subset));
            return;
        }
        subset.add(nums[index]);
        createSubset(nums, index + 1, subset, res);
        subset.remove(subset.size() - 1);
        createSubset(nums, index + 1, subset, res);
    }
}

JavaScript

var subsets = function(nums) {
    const res = [];
    const subset = [];
    const createSubset = function(i) {
        if (i === nums.length) {
            res.push([...subset]);
            return;
        }
        subset.push(nums[i]);
        createSubset(i + 1);
        subset.pop();
        createSubset(i + 1);
    };
    createSubset(0);
    return res;    
};