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.
1import java.util.ArrayList;
2import java.util.List;
3
4public class Solution {
5 public List<List<Integer>> subsets(int[] nums) {
6 List<List<Integer>> result = new ArrayList<>();
7 backtrack(nums, result, new ArrayList<>(), 0);
8 return result;
9 }
10
11 private void backtrack(int[] nums, List<List<Integer>> result, List<Integer> current, int start) {
12 result.add(new ArrayList<>(current));
13 for (int i = start; i < nums.length; i++) {
14 current.add(nums[i]);
15 backtrack(nums, result, current, i + 1);
16 current.remove(current.size() - 1);
17 }
18 }
19
20 public static void main(String[] args) {
21 Solution sol = new Solution();
22 int[] nums = {1, 2, 3};
23 List<List<Integer>> result = sol.subsets(nums);
24
25 for (List<Integer> subset : result) {
26 System.out.println(subset);
27 }
28 }
29}
30In this Java implementation, we utilize a recursive backtracking approach. The 'backtrack' method iteratively decides whether to include each element, building up the current subset, and then explores further possibilities recursively.
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.
1#include <iostream>
2#include <vector>
std::vector<std::vector<int>> subsets(const std::vector<int>& nums) {
int subsetCount = 1 << nums.size();
std::vector<std::vector<int>> result;
for (int i = 0; i < subsetCount; ++i) {
std::vector<int> subset;
for (int j = 0; j < nums.size(); ++j) {
if (i & (1 << j)) {
subset.push_back(nums[j]);
}
}
result.push_back(subset);
}
return result;
}
int main() {
std::vector<int> nums = {1, 2, 3};
std::vector<std::vector<int>> result = subsets(nums);
for (const auto& subset : result) {
std::cout << "[";
for (int num : subset) {
std::cout << num << " ";
}
std::cout << "]\n";
}
return 0;
}
This implementation in C++ applies bit manipulation where 'subsetCount' stands as a numeric representation total for all subsets. Bitwise logic determines element integration within subsequent subsets.