Sponsored
Sponsored
This approach utilizes the concept of recursive backtracking to explore all potential subsets. We start with an empty list and progressively build subsets by either including or excluding each element.
Time Complexity: O(2^n * n), where n is the length of nums. We have 2^n subsets, and copying each subset takes O(n).
Space Complexity: O(n), where n is the depth of the recursion stack.
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 void backtrack(std::vector<int>& nums, std::vector<std::vector<int>>& result, std::vector<int>& current, int start) {
7 result.push_back(current);
8 for (int i = start; i < nums.size(); i++) {
9 current.push_back(nums[i]);
10 backtrack(nums, result, current, i + 1);
11 current.pop_back();
12 }
13 }
14
15 std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
16 std::vector<std::vector<int>> result;
17 std::vector<int> current;
18 backtrack(nums, result, current, 0);
19 return result;
20 }
21};
22
23int main() {
24 Solution sol;
25 std::vector<int> nums = {1, 2, 3};
26 std::vector<std::vector<int>> result = sol.subsets(nums);
27
28 for (const auto& subset : result) {
29 std::cout << "[";
30 for (int i = 0; i < subset.size(); ++i) {
31 std::cout << subset[i];
32 if (i < subset.size() - 1) std::cout << ", ";
33 }
34 std::cout << "]\n";
35 }
36 return 0;
37}
38This C++ solution employs recursive backtracking to generate subsets. The 'backtrack' function includes or excludes each element as we traverse the list and keeps appending the generated subsets to the result vector.
This approach takes advantage of bit manipulation to enumerate subsets. Each subset can correspond to a binary number where each bit decides if an element is present in the subset:
Time Complexity: O(2^n * n), mapping to subset enumeration.
Space Complexity: O(1), as it utilizes constants.
1const subsets
In JavaScript iteration over a complete subset count translated to binary bits selects index proximities for each element in derived subsets. It harnesses shifts to ensure discerning subset computations.