
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
- Initialization:
- Create an empty list
res
to store the final subsets. - Create an empty listsubset
to store the current subset being constructed. - Recursive Function:
- Define a helper method
createSubset
that takes the current indexindex
, the current subset being constructed, and the result listres
. - If the current indexindex
equals the length ofnums
, add a copy of the current subset to the result list and return. - Add the current elementnums[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. - 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;
};