Dare2Solve
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.
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.
Initialization:
res
to store the final subsets.subset
to store the current subset being constructed.Recursive Function:
createSubset
that takes the current index index
, the current subset being constructed, and the result list res
.index
equals the length of nums
, add a copy of the current subset to the result list and return.nums[index]
to the subset and call the function recursively with the next index.Return the Result:
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.
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.
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.
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<int> subset;
createSubset(nums, 0, subset, res);
return res;
}
private:
void createSubset(vector<int>& nums, int i, vector<int>& subset, vector<vector<int>>& 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);
}
};
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)
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> subset = new ArrayList<>();
createSubset(nums, 0, subset, res);
return res;
}
private void createSubset(int[] nums, int index, List<Integer> subset, List<List<Integer>> 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);
}
}
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;
};